package cn.xie.wrench;

import java.util.*;

/**
 * @author: xiaoxie
 * create: 2025-05-13 21:01
 * @BelongsProject: qiuzhaoshuati
 * @BelongsPackage: cn.xie.wrench
 * description: 力扣100题
 */
public class LeetCode {
    /**
     * 灵神相向双指针例题
     * 167. 两数之和 II - 输入有序数组
     * <a href="https://leetcode.cn/problems/two-sum-ii-input-array-is-sorted/description/">...</a>
     * 时间复杂度 O(n) 空间 O(1)
     *
     * @param numbers
     * @param target
     * @return
     */
    public int[] twoSum(int[] numbers, int target) {
        // 非递减顺序排列  所以使用相向双指针 可以减少时间复杂度 从 暴力的 O(n^ 2) - O(n)
        int left = 0, right = numbers.length - 1;
        while (left < right) {
            int x = numbers[left] + numbers[right];
            if (x < target) {
                left++;
            } else if (x == target) {
                break;
            } else {
                right--;
            }
        }
        List<List<Integer>> ans = new ArrayList<>();

        return new int[]{left + 1, right + 1};
    }

    /**
     * 灵神相向双指针例题
     * 15. 三数之和
     * <a href="https://leetcode.cn/problems/3sum/description/">...</a>
     * 时间复杂度 O(n ^ 2) 空间 O(1)
     *
     * @description:
     * @author: xiaoxie
     * @date: 2025/5/13 下午9:40
     * @param: [nums]
     * @return: java.util.List<java.util.List < java.lang.Integer>>
     **/
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        //先进行排序
        Arrays.sort(nums);
        // 为 0 且不重复的
        int n = nums.length;
        for (int i = 0; i < n - 2; i++) {
            int x = nums[i];
            // 为了保证三元组不重复
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            if (x + nums[i + 1] + nums[i + 2] > 0) {
                break;
            }
            if (x + nums[n - 1] + nums[n - 2] < 0) {
                continue;
            }
            int j = i + 1;
            int k = n - 1;
            while (j < k) {
                int s = nums[j] + x + nums[k];
                if (s == 0) {
                    ans.add(new ArrayList<>(Arrays.asList(x, nums[j], nums[k])));
                    do {
                        j++;
                    } while (j < k && nums[j] == nums[j - 1]);
                    do {
                        k--;
                    } while (k > j && nums[k] == nums[k + 1]);
                } else if (s < 0) {
                    j++;
                } else {
                    k--;
                }
            }
        }
        return ans;
    }

    /**
     * 灵神相向双指针练习题
     * 2824. 统计和小于目标的下标对数目
     * <a href="https://leetcode.cn/problems/count-pairs-whose-sum-is-less-than-target/description/">...</a>
     * 时间复杂度 O(NlogN) 空间 O(1)
     *
     * @description:
     * @author: xiaoxie
     * @date: 2025/5/13 下午9:55
     * @param: [nums, target]
     * @return: int
     **/
    public int countPairs(List<Integer> nums, int target) {
        // i != j 数目  由于是数目所以不考虑下标的顺序 所以可以进行排序之后使用
        // 相向双指针
        // 直接对List进行排序
        Collections.sort(nums);
        int res = 0;
        int i = 0, j = nums.size() - 1;
        while (i < j) {
            int s = nums.get(i) + nums.get(j);
            if (s < target) {
                // 1 2 3 4  6
                res += j - i;
                i++;
            } else {
                j--;
            }
        }
        return res;
    }

    /**
     * 灵神相向双指针练习题
     * 16. 最接近的三数之和
     * <a href="https://leetcode.cn/problems/3sum-closest/description/">...</a>
     * 时间复杂度 O(n ^ 2) 空间 O(1)
     *
     * @description:
     * @author: xiaoxie
     * @date: 2025/5/13 下午10:20
     * @param: [nums, target]
     * @return: int
     **/
    public int threeSumClosest(int[] nums, int target) {
        /**
         int res = -10001
         s = x + nums[j] + nums[k]
         if s == t   return t;
         更新和记录最接近的值
         if s < t   j++
         if s > t   k --
         */
        Arrays.sort(nums);
        int n = nums.length;
        int res = nums[0] + nums[1] + nums[2]; // 初始化为数组中可能的最小和
        for (int i = 0; i < n - 2; i++) {
            int x = nums[i];
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int j = i + 1;
            int k = n - 1;
            while (j < k) {
                int s = x + nums[j] + nums[k];
                if (s == target) {
                    return target;
                }
                int diff = Math.abs(s - target);
                if (diff < Math.abs(res - target)) {
                    res = s; // 更新最接近的和
                }
                if (s < target) {
                    j++; // 需要更大的和，移动左指针
                } else {
                    k--; // 需要更小的和，移动右指针
                }
            }
        }
        return res;
    }

    /**
     * 灵神相向双指针练习题
     * 18. 四数之和
     * <a href="https://leetcode.cn/problems/4sum/description/">...</a>
     * 时间复杂度 O(n ^ 3) 空间 O(1)
     *
     * @description:
     * @author: xiaoxie
     * @date: 2025/5/13 下午10:43
     * @param: [nums, target]
     * @return: java.util.List<java.util.List < java.lang.Integer>>
     **/
    public List<List<Integer>> fourSum(int[] nums, int target) {
        // 条件 :  不重复 任意顺序
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        int n = nums.length;
        for (int i = 0; i < n - 3; i++) {
            int x = nums[i];
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            if ((long) x + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {
                break;
            }
            if ((long) x + nums[n - 1] + nums[n - 2] + nums[n - 3] < target) {
                continue;
            }
            for (int j = i + 1; j < n - 2; j++) {
                int y = nums[j];
                if (j > i + 1 && nums[j] == nums[j - 1]) {
                    continue;
                }
                if ((long) x + y + nums[j + 1] + nums[j + 2] > target) {
                    break;
                }
                if ((long) x + y + nums[n - 1] + nums[n - 2] < target) {
                    continue;
                }
                int k = j + 1;
                int l = n - 1;
                while (k < l) {
                    long s = (long) (x + y + nums[k] + nums[l]);
                    if (s == target) {
                        res.add(new ArrayList<>(Arrays.asList(x, y, nums[k], nums[l])));
                        do {
                            k++;
                        } while (k < l && nums[k] == nums[k - 1]);

                        do {
                            l--;
                        } while (k < l && nums[l] == nums[l + 1]);
                    } else if (s < target) {
                        k++;
                    } else {
                        l--;
                    }
                }
            }
        }
        return res;
    }

    /**
     * 灵神相向双指针练习题
     * 611. 有效三角形的个数
     * <a href="https://leetcode.cn/problems/valid-triangle-number/description/">...</a>
     * 时间复杂度 O(n ^ 2) 空间 O(1)
     *
     * @description:
     * @author: xiaoxie
     * @date: 2025/5/13 下午11:03
     * @param: [nums]
     * @return: int
     **/
    public int triangleNumber(int[] nums) {
        /**
         任意两边之和必须大于第三边。
         可以重复,计算数目
         i = 第三条边
         (j + k) > i;
         1 2 3 5 6
         i
         */
        int res = 0;
        Arrays.sort(nums);
        int n = nums.length;
        for (int i = n - 1; i > 1; i--) {
            int x = nums[i];
            if (nums[i - 1] + nums[i - 2] < x) {
                continue;
            }
            int j = 0;
            int k = i - 1;
            while (j < k) {
                int s = nums[j] + nums[k];
                if (s > x) {
                    res += k - j;
                    k--;
                } else {
                    j++;
                }
            }
        }
        return res;
    }

    /**
     * @description: 灵神相向双指针例题
     * 11. 盛最多水的容器
     * <a href="https://leetcode.cn/problems/container-with-most-water/">...</a>
     * 时间复杂度 O(n) 空间: O(1)
     * @author: xiaoxie
     * @date: 2025/5/14 下午10:03
     * @param: [height]
     * @return: int
     **/
    public int maxArea(int[] height) {
        // 使用双指针 l = 0 , r= n-1 如果 l 的 高度小于 r 的 高度,那么 l++ 否则 r--;
        int n = height.length;
        int ans = 0, left = 0, right = n - 1;
        while (left < right) {
            int s = (right - left) * Math.min(height[left], height[right]);
            ans = Math.max(s, ans);
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return ans;
    }

    /**
     * @description: 灵神相向双指针例题
     * 42. 接雨水
     * <a href="https://leetcode.cn/problems/trapping-rain-water/description/">...</a>
     * 时间复杂度: O(n), 空间复杂度 O(1)
     * @author: xiaoxie
     * @date: 2025/5/14 下午10:13
     * @param: [height]
     * @return: int
     **/
    public int trap(int[] height) {
        /**
         这题可以把每个位置都看成一个水桶 那么这个水桶可以装水的容量取决于前缀的最大值和后缀最大值
         之间的最小值.
         并且可以边更新边计算容量
         */
        int pre_max = 0, suf_max = 0, ans = 0;
        int n = height.length;
        int left = 0, right = n - 1;
        while (left < right) {
            // 首先更新前缀和后缀
            pre_max = Math.max(height[left], pre_max);
            suf_max = Math.max(height[right], suf_max);
            if (pre_max < suf_max) {
                ans += pre_max - height[left];
                left++;
            } else {
                ans += suf_max - height[right];
                right--;
            }
        }
        return ans;
    }

    /**
     * @description: 双指针热题100
     * 283. 移动零
     * <a href="https://leetcode.cn/problems/move-zeroes/description/?envType=study-plan-v2&envId=top-100-liked">...</a>
     * 时间复杂度 O(n) 空间复杂度 O(1)
     * @author: xiaoxie
     * @date: 2025/5/14 下午10:31
     * @param: [nums]
     * @return: void
     **/
    public void moveZeroes(int[] nums) {
        /**
         把数组分为三部分 [0,index] 非0 [index,dest] 为 0, [dest, n-1] 为待处理区

         */
        int index = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                nums[index++] = nums[i];
            }
        }
        for (int i = index; i < nums.length; i++) {
            nums[i] = 0;
        }

    }

    /**
     * @description: 双指针热题100
     * 11. 盛最多水的容器
     * <a href="https://leetcode.cn/problems/container-with-most-water/description/?envType=study-plan-v2&envId=top-100-liked">...</a>
     * 时间 O(n) 空间 O(1)
     * @author: xiaoxie
     * @date: 2025/5/14 下午10:38
     * @param: [height]
     * @return: int
     **/
    public int maxArea1(int[] height) {
        int n = height.length;
        int ans = 0, left = 0, right = n - 1;
        while (left < right) {
            int s = (right - left) * Math.min(height[left], height[right]);
            ans = Math.max(s, ans);
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return ans;
    }

    /**
     * @description: 双指针热题100
     * 15. 三数之和
     * <a href="https://leetcode.cn/problems/3sum/description/?envType=study-plan-v2&envId=top-100-liked">...</a>
     * 时间 O(N ^ 2) 空间 O(1)
     * @author: xiaoxie
     * @date: 2025/5/14 下午10:48
     * @param: [nums]
     * @return: java.util.List<java.util.List < java.lang.Integer>>
     **/
    public List<List<Integer>> threeSum1(int[] nums) {
        // 先排序
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<>();
        // 先确定好一位数
        int n = nums.length;
        for (int i = 0; i < n - 2; i++) {
            // 避免重复
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            // 优化
            if (nums[i] + nums[i + 1] + nums[i + 2] > 0) break;
            if (nums[i] + nums[n - 1] + nums[n - 2] < 0) continue;
            int j = i + 1, k = n - 1;
            while (j < k) {
                if (nums[i] + nums[j] + nums[k] == 0) {
                    ans.add(new ArrayList<>(Arrays.asList(nums[i], nums[j], nums[k])));
                    do {
                        j++;
                    } while (j < k && nums[j] == nums[j - 1]);
                    do {
                        k--;
                    } while (j < k && nums[k] == nums[k + 1]);

                } else if (nums[i] + nums[j] + nums[k] > 0) {
                    k--;
                } else {
                    j++;
                }
            }
        }
        return ans;
    }

    /**
     * @description: 双指针热题100
     * 42. 接雨水
     * <a href="https://leetcode.cn/problems/trapping-rain-water/description/?envType=study-plan-v2&envId=top-100-liked">...</a>
     * 空间 O(n) 时间 O(1)
     * @author: xiaoxie
     * @date: 2025/5/14 下午10:54
     * @param: [height]
     * @return: int
     **/
    public int trap1(int[] height) {
        int n = height.length;
        int pre_max = 0, suf_max = 0, left = 0, right = n - 1;
        int ans = 0;
        while (left < right) {
            // 先更新前缀和后缀
            pre_max = Math.max(pre_max, height[left]);
            suf_max = Math.max(suf_max, height[right]);
            if (pre_max < suf_max) {
                ans += pre_max - height[left];
                left++;
            } else {
                ans += suf_max - height[right];
                right--;
            }
        }
        return ans;
    }

    /**
     * @description: 同向双指针 即 滑动窗口 灵神例题
     * 209. 长度最小的子数组
     * <a href="https://leetcode.cn/problems/minimum-size-subarray-sum/description/">...</a>
     * 时间复杂度 O(n) 时间 O(1)
     * @author: xiaoxie
     * @date: 2025/5/15 下午10:14
     * @param: [target, nums]
     * @return: int
     **/
    public int minSubArrayLen(int target, int[] nums) {
        // 相向双指针 即滑动窗口
        int n = nums.length;
        int ans = n + 1;
        int left = 0, sum = 0;
        for (int right = 0; right < n; right++) {
            sum += nums[right];
            while (sum >= target) {
                // 因为 都是正数 所以 letf > right 不会出现
                ans = Math.min(ans, right - left + 1);
                sum -= nums[left];
                left++;
            }
        }
        return ans == n + 1 ? 0 : ans;
    }

    /**
     * @description: 同向双指针 即 滑动窗口 灵神例题
     * 3. 无重复字符的最长子串
     * <a href="https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/">...</a>
     * 空间 O(N) 时间 O(128) 即 O(1)
     * @author: xiaoxie
     * @date: 2025/5/15 下午10:25
     * @param: [s]
     * @return: int
     **/
    public int lengthOfLongestSubstring(String s) {
        // 先使用 长度为 128 的数组 记录 每个字符 出现次数 使用滑动窗口找到
        int[] hash = new int[128];
        int ans = 0;
        int left = 0;
        for (int right = 0; right < s.length(); right++) {
            hash[128 - s.charAt(right)]++;
            while (hash[128 - s.charAt(right)] > 1) {
                hash[128 - s.charAt(left)]--;
                left++;
            }
            ans = Math.max(ans, right - left + 1);
        }
        return ans;
    }

    /**
     * @description: 同向双指针 即 滑动窗口 灵神例题
     * 713. 乘积小于 K 的子数组
     * <a href="https://leetcode.cn/problems/subarray-product-less-than-k/description/">...</a>
     * 空间 O(N) 时间 O(1)
     * @author: xiaoxie
     * @date: 2025/5/15 下午10:43
     * @param: [nums, k]
     * @return: int
     **/
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        // 正数 先满足后变成不满足  滑动窗口
        // 假如 [l,r] < k 那么 数目为 [l+1,r],[l+2,r]...[r,r] 即 r - l + 1;
        if (k <= 1) {
            return 0;
        }
        int ans = 0;
        int res = 1, left = 0;
        for (int right = 0; right < nums.length; right++) {
            res *= nums[right];
            while (res >= k) {
                res /= nums[left];
                left++;
            }
            ans += right - left + 1;
        }
        return ans;
    }

    /**
     * @description: 同向双指针 即 滑动窗口 灵神例题
     * 2958. 最多 K 个重复元素的最长子数组
     * <a href="https://leetcode.cn/problems/length-of-longest-subarray-with-at-most-k-frequency/description/">...</a>
     * 时间 O(n) 空间 O(n)
     * @author: xiaoxie
     * @date: 2025/5/16 下午8:13
     * @param: [nums, k]
     * @return: int
     **/
    public int maxSubarrayLength(int[] nums, int k) {
        /**
         使用同向双指针 由不满足到满足 1 <= nums[i] <= 109
         */
        int ans = 0, left = 0;
        HashMap<Integer, Integer> hash = new HashMap<>();
        for (int right = 0; right < nums.length; right++) {
            hash.put(nums[right], hash.getOrDefault(nums[right], 0) + 1);
            while (hash.get(nums[right]) > k) {
                hash.put(nums[left], hash.get(nums[left]) - 1);
                left++;
            }
            ans = Math.max(ans, right - left + 1);
        }
        return ans;
    }

    /**
     * @description: 同向双指针 即 滑动窗口 灵神例题
     * 2730. 找到最长的半重复子字符串
     * <a href="https://leetcode.cn/problems/find-the-longest-semi-repetitive-substring/description/">...</a>
     * 时间 O(N) 时间 O(1)
     * @author: xiaoxie
     * @date: 2025/5/16 下午8:43
     * @param: [s]
     * @return: int
     **/
    public int longestSemiRepetitiveSubstring(String s) {
        /**
         至多有一对相邻字符是相等 "0010" 、"002020" 、"0123" 、"2002" 和 "54944" 是半重复字符串
         "00101022" （相邻的相同数字对是 00 和 22）不是
         这题使用 同向双指针 即滑动窗口 难点是如何表示 只能有一个 相邻字符重复
         我的想法是就使用一个如 same 来表示 相邻字符相等的数量
         if(right > 0 && s.right == s.right -1)
         same++;
         后续就是不满足变成满足
         */
        int ans = 0, left = 0;
        int same = 0;
        char[] str = s.toCharArray();
        for (int right = 0; right < s.length(); right++) {
            if (right > 0 && str[right] == str[right - 1]) {
                same++;
            }
            while (same > 1) {
                if (left < right && str[left] == str[left + 1]) {
                    same--;
                }
                left++;
            }
            ans = Math.max(ans, right - left + 1);
        }
        return ans;
    }

    /**
     * @description: 同向双指针 即 滑动窗口 灵神例题
     * 1004. 最大连续1的个数 III
     * <a href="https://leetcode.cn/problems/max-consecutive-ones-iii/description/">...</a>
     * 空间 O(N) 时间 O(1)
     * @author: xiaoxie
     * @date: 2025/5/16 下午8:50
     * @param: [nums, k]
     * @return: int
     **/
    public int longestOnes(int[] nums, int k) {
        // 可以把题目理解为  至多有k个0 的最长子数组
        int zero = 0, ans = 0, left = 0;
        for (int right = 0; right < nums.length; right++) {
            if (nums[right] == 0) {
                zero++;
            }
            while (zero > k) {
                if (nums[left] == 0) {
                    zero--;
                }
                left++;
            }
            ans = Math.max(ans, right - left + 1);
        }
        return ans;
    }

    /**
     * @description: 同向双指针 即 滑动窗口 灵神例题
     * 2962. 统计最大元素出现至少 K 次的子数组
     * <a href="https://leetcode.cn/problems/count-subarrays-where-max-element-appears-at-least-k-times/description/">...</a>
     * 时间 O(N) 空间 O(1)
     * @author: xiaoxie
     * @date: 2025/5/16 下午9:15
     * @param: [nums, k]
     * @return: long
     **/
    public long countSubarrays1(int[] nums, int k) {
        /**
         先找到最大元素后 使用 同向双指针 滑动窗口
         满足到不满足
         */
        int max = 0, left = 0, count = 0;
        long ans = 0;
        for (int s : nums) {
            max = Math.max(max, s);
        }
        for (int right = 0; right < nums.length; right++) {
            if (nums[right] == max) {
                count++;
            }
            while (count >= k) {
                // 这里其实表示如果前面的满足了至少出现k次那么后续的不管是什么都满足条件
                ans += (long) nums.length - right;
                if (nums[left] == max) {
                    count--;
                }
                left++;
            }
        }
        return ans;
    }

    /**
     * @description: 同向双指针 即 滑动窗口 灵神例题
     * 2302. 统计得分小于 K 的子数组数目
     * <a href="https://leetcode.cn/problems/count-subarrays-with-score-less-than-k/description/">...</a>
     * 时间 O(n) 空间 O(1)
     * @author: xiaoxie
     * @date: 2025/5/16 下午10:09
     * @param: [nums, k]
     * @return: long
     **/
    public long countSubarrays(int[] nums, long k) {
        long ans = 0;
        long sum = 0;
        int left = 0;
        for (int right = 0; right < nums.length; right++) {
            sum += nums[right];
            while (sum * (right - left + 1) >= k) {
                sum -= nums[left];
                left++;
            }
            ans += right - left + 1;
        }
        return ans;
    }

    /**
     * @description: 同向双指针 即 滑动窗口 灵神例题
     * 1658. 将 x 减到 0 的最小操作数
     * <a href="https://leetcode.cn/problems/minimum-operations-to-reduce-x-to-zero/description/">...</a>
     * 时间 O(n) 空间 O(1)
     * @author: xiaoxie
     * @date: 2025/5/16 下午10:30
     * @param: [nums, x]
     * @return: int
     **/
    public int minOperations(int[] nums, int x) {
        /**
         每一次操作时，你应当移除数组 nums 最左边或最右边的元素
         然后从 x 中减去该元素的值 将 x 恰好 减到 0 ，返回 最小操作数
         可以 转换成 等于k(sum - x  = k ) 的 最长子数组
         不满足到满足
         */
        int sum = 0, ans = -1, left = 0;
        for (int s : nums) {
            sum += s;
        }
        if (sum - x < 0) {
            return -1;
        }
        int s = 0;
        for (int right = 0; right < nums.length; right++) {
            s += nums[right];
            while (s > sum - x) {
                s -= nums[left];
                left++;
            }
            if (s == sum - x) {
                ans = Math.max(ans, right - left + 1);
            }
        }
        return ans == -1 ? -1 : nums.length - ans;
    }

    /**
     * @description: 同向双指针 即 滑动窗口 灵神例题
     * 76. 最小覆盖子串
     * <a href="https://leetcode.cn/problems/minimum-window-substring/">...</a>
     * 时间 O(n + m) 空间 O(1)
     * @author: xiaoxie
     * @date: 2025/5/16 下午11:03
     * @param: [s, t]
     * @return: java.lang.String
     **/
    public String minWindow(String s, String t) {
        /**
         一个字符串 s 、一个字符串 t
         最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 ""
         */
        if (t.length() > s.length()) {
            return new String();
        }
        int len = 0x3f3f3f3f;
        int minleft = 0, same = 0;
        int left = 0;
        int[] hash = new int[128];
        char[] chT = t.toCharArray();
        char[] chS = s.toCharArray();
        for (char ch : chT) {
            hash[128 - ch]++;
            same++;
        }
        for (int right = 0; right < s.length(); right++) {
            if (hash[128 - chS[right]]-- > 0) {
                same--;
            }
            while (same == 0) {
                if (len > right - left + 1) {
                    minleft = left;
                    len = right - left + 1;
                }
                if (hash[128 - chS[left]]++ == 0) {
                    same++;
                }
                left++;
            }
        }
        return len == 0x3f3f3f3f ? new String() : s.substring(minleft, minleft + len);
    }

    /**
     * @description: 力扣热题100 同向双指针 即 滑动窗口
     * 3. 无重复字符的最长子串
     * <a href="https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/?envType=study-plan-v2&envId=top-100-liked">...</a>
     * 时间 O(N) 空间 O(1)
     * @author: xiaoxie
     * @date: 2025/5/16 下午11:09
     * @param: [s]
     * @return: int
     **/
    public int lengthOfLongestSubstring1(String s) {
        /**
         不满足到满足
         */
        int[] hash = new int[128];
        int ans = 0, left = 0;
        char[] ch = s.toCharArray();
        for (int right = 0; right < s.length(); right++) {
            hash[128 - ch[right]]++;
            while (hash[128 - ch[right]] > 1) {
                hash[128 - ch[left]]--;
                left++;
            }
            ans = Math.max(ans, right - left + 1);
        }
        return ans;
    }

    /**
     * @description: 力扣热题100 同向双指针 即 滑动窗口
     * 438. 找到字符串中所有字母异位词
     * <a href="https://leetcode.cn/problems/find-all-anagrams-in-a-string/description/?envType=study-plan-v2&envId=top-100-liked">...</a>
     * 时间 O(N) 空间 O(1)
     * @author: xiaoxie
     * @date: 2025/5/16 下午11:40
     * @param: [s, p]
     * @return: java.util.List<java.lang.Integer>
     **/
    public List<Integer> findAnagrams(String s, String p) {
        if (p.length() > s.length()) {
            return new ArrayList<>(Arrays.asList());
        }
        int[] hash = new int[26];
        char[] chP = p.toCharArray();
        int left = 0;
        List<Integer> ans = new ArrayList<>();
        for (char ch : chP) {
            hash[ch - 'a']++;
        }
        char[] chS = s.toCharArray();
        for (int right = 0; right < s.length(); right++) {
            hash[chS[right] - 'a']--;
            while (hash[chS[right] - 'a'] < 0) {
                hash[chS[left] - 'a']++;
                left++;
            }
            if (right - left + 1 == p.length()) {  // s' 和 p 的每种字母的出现次数都相同
                ans.add(left);
            }
        }
        return ans;
    }

    /**
     * @description: 灵神 二分查找 视频例题
     * 34. 在排序数组中查找元素的第一个和最后一个位置
     * <a href="https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/description/">...</a>
     * 时间 O(logN) 空间 O(1)
     * @author: xiaoxie
     * @date: 2025/5/18 下午10:11
     * @param: [nums, target]
     * @return: int
     **/
    private int search(int[] nums, int target) {
        // 这个是开区间
        int left = -1;
        int right = nums.length;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                //  (left,mid) < target
                left = mid;
            } else {
                // (mid,right) >= target
                right = mid;
            }
            // left < target  left + 1 = right
            // 所以返回right
        }
        return right;
    }

    public int[] searchRange(int[] nums, int target) {
        // 使用 二分
        int start = search(nums, target);
        if (start == nums.length || nums[start] != target) {
            return new int[]{-1, -1};
        }
        // <= target + 1 的位置 - 1
        int end = search(nums, target + 1) - 1;
        return new int[]{start, end};
    }

    /**
     * @description: 灵神 二分查找 视频例题
     * 2529. 正整数和负整数的最大计数
     * <a href="https://leetcode.cn/problems/maximum-count-of-positive-integer-and-negative-integer/description/">...</a>
     * 时间 O(logN) 空间 O(1)
     * @author: xiaoxie
     * @date: 2025/5/18 下午10:28
     * @param: [nums]
     * @return: int
     **/
    public int maximumCount(int[] nums) {
        /**
         同样也是调用两次 二分查找
         一个是 < 0
         一个是 > 0
         由于都是正整数
         所以 < 0   >= 0  - 1; 个数 = 下标 + 1
         > 0   >= 1 ;  个数 = n - 下标;
         */

        return Math.max(search(nums, 0), nums.length - search(nums, 1));
    }

    private int search(int[] nums, long target) {
        int left = -1;
        int right = nums.length;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid;
            } else {
                right = mid;
            }
        }
        return right;
    }

    /**
     * @description: 灵神 二分查找 视频例题
     * 2300. 咒语和药水的成功对数
     * <a href="https://leetcode.cn/problems/successful-pairs-of-spells-and-potions/description/">...</a>
     * 时间 O(NlogN) 空间 O(N)
     * @author: xiaoxie
     * @date: 2025/5/18 下午10:51
     * @param: [spells, potions, success]
     * @return: int[]
     **/
    public int[] successfulPairs(int[] spells, int[] potions, long success) {
        /**
         1. 由于是求数目那么就可以使用排序 使用 二分 或者是双指针(更适合求最大或者最小) 都可以写
         2. target success / spells[i]  + 1 向上取整
         3. ans =  n - index
         */
        Arrays.sort(potions);
        for (int i = 0; i < spells.length; i++) {
            // 向上取整
            long target = (success + spells[i] - 1) / spells[i];
            spells[i] = potions.length - search(potions, target);
        }
        return spells;
    }

    /**
     * @description: 灵神 二分查找 视频例题
     * 2563. 统计公平数对的数目
     * <a href="https://leetcode.cn/problems/count-the-number-of-fair-pairs/description/">...</a>
     * 时间: O(NlogN) 空间 O(1)
     * @author: xiaoxie
     * @date: 2025/5/19 下午10:48
     * @param: [nums, lower, upper]
     * @return: long
     **/
    public long countFairPairs(int[] nums, int lower, int upper) {
        Arrays.sort(nums);
        long ans = 0;
        for (int i = 1; i < nums.length; i++) {
            int r = lowerBound(nums, i, upper - nums[i] + 1);
            int l = lowerBound(nums, i, lower - nums[i]);
            ans += r - l;
        }
        return ans;
    }

    private int lowerBound(int[] nums, int right, int target) {
        int left = -1;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] >= target) {
                right = mid;
            } else {
                left = mid;
            }
        }
        return right;
    }

    /**
     * @description: 灵神 二分查找 视频例题
     * 275. H 指数 II
     * <a href="https://leetcode.cn/problems/h-index-ii/description/">...</a>
     * 时间 O(logN) 时间 O(1)
     * @author: xiaoxie
     * @date: 2025/5/20 下午10:46
     * @param: [citations]
     * @return: int
     **/
    public int hIndex(int[] citations) {
        /**
         其实这题本质上是求h的二分 假如 c数组为[0,1,3,5,6]
         所以 h数组就为[1,2,3,4,5]
         所以开区间写法写成(0,n+1)
         c作为辅助数组来使用
         */
        int n = citations.length;
        int left = 0, right = n + 1;
        while (left + 1 < right) {
            // 循环不变量：
            // left 的回答一定为「是」
            // right 的回答一定为「否」
            int mid = left + (right - left) / 2;
            if (citations[n - mid] >= mid) {
                left = mid;
            } else {
                right = mid;
            }
        }
        return left;
    }

    /**
     * @description: 灵神 二分查找 视频练习题
     * 875. 爱吃香蕉的珂珂
     * <a href="https://leetcode.cn/problems/koko-eating-bananas/description/">...</a>
     * 时间复杂度 O(nlogU) 这里的U是piles数组的长度 空间 O(1)
     * @author: xiaoxie
     * @date: 2025/5/26 下午4:45
     * @param: [piles, h]
     * @return: int
     **/
    public int minEatingSpeed(int[] piles, int h) {
        /**
         如果 珂珂可以在 k 的速度下吃掉香蕉,那么在k+1,k+2 的速度下肯定可以吃掉
         即找到(1,max(p)) 中可以在h小时吃掉所有香蕉的最小速度
         right为可以吃掉的速度k
         left 都为不可以
         */
        int max = 0;
        for (int p : piles) {
            max = Math.max(max, p);
        }

        int left = 0;
        int right = max + 1;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (check(piles, mid, h)) {
                right = mid;
            } else {
                left = mid;
            }
        }
        return right;
    }

    private boolean check(int[] piles, int k, int h) {
        int sum = piles.length;
        for (int p : piles) {
            sum += (p - 1) / k;
            if (sum > h) {
                return false;
            }
        }
        return true;
    }

    /**
     * @description: 灵神 二分查找 视频练习题
     * 2187. 完成旅途的最少时间
     * <a href="https://leetcode.cn/problems/minimum-time-to-complete-trips/description/">...</a>
     * 时间复杂度 O(nlogU) 这里的U是time数组的长度 空间 O(1)
     * @author: xiaoxie
     * @date: 2025/5/26 下午5:19
     * @param: [time, totalTrips]
     * @return: long
     **/
    public long minimumTime(int[] time, int totalTrips) {
        /**
         time[i] 表示第 i 辆公交车完成 一趟旅途 所需要花费的时间
         如果 time = k 可以完成 那么 k + 1,k + 2都可以完成
         如果 time = k 不可以完成,那么 k -1 .k-2 也不可以完成
         构成单调性 可以使用二分
         那么时间的范围为(min(time),min(time) * total(都只让最快的车跑))
         */
        //
        int min = Integer.MAX_VALUE;
        for (int t : time) {
            min = Math.min(min, t);
        }
        long left = min - 1;
        long right = (long) min * totalTrips + 1;
        // (left,right)
        while (left + 1 < right) {
            long mid = left + (right - left) / 2;
            if (check(time, totalTrips, mid)) {
                right = mid;
            } else {
                left = mid;
            }
        }
        // 循环不变量即 righ 那边的都为true left 为 false
        // 那么 left + 1 == right
        // 一定为最少时间
        return right;
    }

    public boolean check(int[] time, int total, long mid) {
        // 在 mid 时间内是否可以完成
        long sum = 0;
        for (int t : time) {
            sum += mid / t;
            if (sum >= total) {
                return true;
            }
        }
        return false;
    }

    /**
     * @description: 灵神 二分查找 视频练习题
     * 2861. 最大合金数
     * <a href="https://leetcode.cn/problems/maximum-number-of-alloys/description/">...</a>
     * 时间复杂度：O(knlogU)，其中 U=min(stock)+budget。
     * 空间复杂度：O(1)。
     * @author: xiaoxie
     * @date: 2025/5/26 下午6:01
     * @param: [n, k, budget, composition, Stock, Cost]
     * @return: int
     **/
    public int maxNumberOfAlloys(int n, int k, int budget, List<List<Integer>> composition, List<Integer> Stock, List<Integer> Cost) {
        int res = 0;
        int max = Collections.min(Stock) + budget; // 假设所有的金属都花费1 又因为stock是已经拥有的i类金属所以取最小值,即所可以合成的最大金属为这个
        Integer[] stock = Stock.toArray(Integer[]::new);
        Integer[] cost = Cost.toArray(Integer[]::new);
        for (List<Integer> cop : composition) {
            Integer[] comp = cop.toArray(Integer[]::new);
            int left = res;
            int right = max + 1;
            while (left + 1 < right) {
                long money = 0;
                boolean success = true;
                int mid = left + (right - left) / 2;
                for (int i = 0; i < n; i++) {
                    // 如果已拥有的i类金属不够那么就需要花钱
                    if (stock[i] < (long) comp[i] * mid) {
                        money += ((long) comp[i] * mid - stock[i]) * cost[i];
                    }
                    if (money > budget) {
                        success = false;
                        break;
                    }
                }
                if (success) {
                    left = mid;
                } else {
                    right = mid;
                }


            }
            // left 都是可以的,right 都是不可以的
            // left + 1 == right;
            res = left;
        }
        return res;
    }

    /**
     * @description: 灵神 二分查找 视频练习题
     * 2439. 最小化数组中的最大值
     * <a href="https://leetcode.cn/problems/minimize-maximum-of-array/description/">...</a>
     * 时间O(NlogU) U = nums.length 空间 O(1)
     * @author: xiaoxie
     * @date: 2025/5/26 下午6:21
     * @param: [nums]
     * @return: int
     **/
    public int minimizeArrayValue(int[] nums) {
        int left = -1;
        int right = 0;
        for (int num : nums) {
            right = Math.max(right, num);
        }
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (check(nums, mid)) {
                right = mid;
            } else {
                left = mid;
            }
        }
        return right;
    }

    private boolean check(int[] nums, int max) {
        long ex = 0;
        for (int i = nums.length - 1; i > 0; i--) {
            // 判断最多减去多少.
            ex = Math.max(nums[i] + ex - max, 0);
        }
        // 如果 nums[0] + ex > 最大值
        return nums[0] + ex <= max;
    }

    /**
     * @description: 灵神 二分查找 视频练习题
     * 2517. 礼盒的最大甜蜜度
     * <a href="https://leetcode.cn/problems/maximum-tastiness-of-candy-basket/description/">...</a>
     * 时间O(NlogU) U = nums.length 空间 O(1)
     * @author: xiaoxie
     * @date: 2025/5/26 下午6:56
     * @param: [price, k]
     * @return: int
     **/
    public int maximumTastiness(int[] price, int k) {
        /**
         最大值最小化和最小值最大值都可以使用二分
         对于本题, k越小那么甜蜜度越大
         */
        Arrays.sort(price);
        int left = 0;
        int right = price[price.length - 1];
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (select(price, mid) >= k) {
                left = mid;
            } else {
                right = mid;
            }
        }
        return left;
    }

    private int select(int[] price, int mid) {
        int cnt = 1, p = price[0];
        for (int pr : price) {
            if (pr >= p + mid) {
                // 因为求的是绝对差的最小值所以只能是大于的才可以选
                cnt++;
                p = pr;
            }
        }
        return cnt;
    }

    /**
     * @description: 灵神 二分查找 视频练习题
     * 162. 寻找峰值
     * <a href="https://leetcode.cn/problems/find-peak-element/solution/by-endlesscheng-9ass/">...</a>
     * 时间O(logN) 空间 O(1)
     * @author: xiaoxie
     * @date: 2025/5/28 下午9:54
     * @param: [nums]
     * @return: int
     **/
    public int findPeakElement(int[] nums) {
        /**
         使用二分法这里规定:
         红色为峰值的左边
         蓝色为峰值或者为峰值的右边
         那么最后一个数就一定为蓝色
         所以找的范围就为(0,n-2)
         [1,2,3,1]
         */
        int left = -1, n = nums.length;
        int right = n - 1;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[mid + 1]) {
                right = mid;
            } else {
                left = mid;
            }
        }
        return right;
    }

    /**
     * @description: 灵神 二分查找 视频练习题
     * 153. 寻找旋转排序数组中的最小值
     * <a href="https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/description/">...</a>
     * 时间O(logN) 空间 O(1)
     * @author: xiaoxie
     * @date: 2025/5/28 下午10:37
     * @param: [nums]
     * @return: int
     **/
    public int findMin(int[] nums) {
        /**
         无论如何旋转数组最多被分为两种情况
         1. 一个递增数组
         2.两个递增数组
         那么我们规定
         最小值的左边为红色
         最小值及最小值的右边为蓝色
         那么最后一个数一定为蓝色
         我们查找范围为[0,n-2];
         */
        int n = nums.length;
        int left = -1, right = n - 1;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[n - 1]) {
                left = mid;
            } else {
                right = mid;
            }
        }
        return nums[right];
    }

    /**
     * @description: 灵神 二分查找 视频练习题
     * 33. 搜索旋转排序数组
     * <a href="https://leetcode.cn/problems/search-in-rotated-sorted-array/description/">...</a>
     * 时间O(logN) 空间 O(1)
     * @author: xiaoxie
     * @date: 2025/5/28 下午11:16
     * @param: [nums, target]
     * @return: int
     **/
    public int search3(int[] nums, int target) {
        /**
         经过旋转后 数组会分为两种情况
         1.一段递增数组
         2.两段递增数组
         那么我们规定:
         t的左侧为红色
         t及其右边为蓝色
         那么最后一个数一定为蓝色
         范围为[0.n-1]
         */
        int n = nums.length;
        int left = -1, right = n;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (is_blue(nums, mid, target)) {
                right = mid;
            } else {
                left = mid;
            }
        }
        if (right == n || nums[right] != target) {
            return -1;
        }
        return right;
    }

    private boolean is_blue(int[] nums, int mid, int t) {
        int n = nums.length;
        if (nums[mid] > nums[n - 1]) {
            return nums[mid] >= t && t > nums[n - 1];
        } else {
            return nums[mid] >= t || t > nums[n - 1];
        }
    }

    /**
     * @description: 灵神 二分查找 视频练习题
     * 1901. 寻找峰值 II
     * <a href="https://leetcode.cn/problems/find-a-peak-element-ii/description/">...</a>
     * 时间O(m logN) 空间 O(1)
     * 从任意一个点出发，可以经过一个递增路径，找到一个极大值点。
     * <p>
     * 可以按照一列列/排排的进行二分搜索。
     * 找到这列的最大值，然后观察其左侧右侧有没有比它大的。如果没有，那这个点就是一个全局极大值。
     * 如果有，就说明那一侧有一个极大值点。
     * <p>
     * 因为这一侧有一个点大于中间一整列，根据上述事实，如果从它出发走一个递增路径寻找极大值，一定不能越过中间这一列，否则不满足递增要求。
     * 所以可以肯定，这一侧有极大值。
     * <p>
     * 重复这个过程，可以二分搜索定位到只剩一列，这列的最大值就必定是一个极大值点。
     * @author: xiaoxie
     * @date: 2025/5/29 下午9:28
     * @param: [mat]
     * @return: int[]
     **/
    public int[] findPeakGrid(int[][] mat) {
        int left = -1;
        int right = mat.length - 1;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            int j = indexMax(mat[mid]);
            if (mat[mid][j] > mat[mid + 1][j]) {
                right = mid;
            } else {
                left = mid;
            }
        }
        return new int[]{right, indexMax(mat[right])};
    }

    private int indexMax(int[] a) {
        int index = 0;
        for (int i = 0; i < a.length; i++) {
            if (a[i] > a[index]) {
                index = i;
            }
        }
        return index;
    }

    /**
     * @description: 灵神 二分查找 视频练习题
     * 154. 寻找旋转排序数组中的最小值 II
     * <a href="https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array-ii/description/">...</a>
     * 时间O(logN) 空间 O(1)
     * @author: xiaoxie
     * @date: 2025/5/29 下午9:50
     * @param: [nums]
     * @return: int
     **/
    public int findMin1(int[] nums) {
        /**
         还是一样的,因为递增数组
         所以可能分为 一个递增数组
         或者是两个递增数组
         那么我们规定
         最小值左边为红色
         右边及最小值为蓝色
         因为的重复的原因
         那么就是如果nums[mid] == nums[n-1]
         那么直接把nums[n-1]的数给删除
         如果恰好是最小值那么nums[mid] 也为最小值不影响
         那个不是就排除一个数了,这样更好
         */
        int n = nums.length;
        int left = -1;
        int right = n - 1;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[right]) {
                left = mid;
            } else if (nums[mid] == nums[right]) {
                right--;
            } else {
                right = mid;
            }
        }
        return nums[right];
    }

    /**
     * @description: 二分查找100 力扣热题
     * 35. 搜索插入位置
     * <a href="https://leetcode.cn/problems/search-insert-position/description/?envType=study-plan-v2&envId=top-100-liked">...</a>
     * 时间 O(logN)  空间 O(1)
     * @author: xiaoxie
     * @date: 2025/6/1 下午9:08
     * @param: [nums, target]
     * @return: int
     **/
    public int searchInsert(int[] nums, int target) {
        int left = -1, n = nums.length;
        int right = n;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid;
            } else {
                right = mid;
            }
        }
        return left + 1;

    }

    /**
     * @description: 二分查找100 力扣热题
     * <a href="https://leetcode.cn/problems/search-a-2d-matrix/?envType=study-plan-v2&envId=top-100-liked">...</a>
     * 时间 O(LogN) 空间 O(1)
     * 把矩阵每一行拼在一起，我们可以得到一个递增数组。
     * @author: xiaoxie
     * @date: 2025/6/1 下午9:29
     * @param: [matrix, target]
     * @return: boolean
     **/
    public boolean searchMatrix(int[][] matrix, int target) {
        int n = matrix.length, m = matrix[0].length;
        int left = -1;
        int right = n * m;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            int x = matrix[mid / m][mid % m];
            if (x == target) {
                return true;
            } else if (x < target) {
                left = mid;
            } else {
                right = mid;
            }
        }
        return false;
    }

    private int searchRat(int[] nums, int t) {
        int left = -1;
        int right = nums.length;
        // 这里规定 < t 红色 >= t 蓝色 开区间解法
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < t) {
                left = mid;
            } else {
                right = mid;
            }
        }
        return right;
    }

    /**
     * @description: 二分查找100 力扣热题
     * 34. 在排序数组中查找元素的第一个和最后一个位置
     * <a href="https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/description/?envType=study-plan-v2&envId=top-100-liked">...</a>
     * 时间 O(LogN) 空间 O(1)
     * @author: xiaoxie
     * @date: 2025/6/1 下午9:58
     * @param: [nums, target]
     * @return: int[]
     **/
    public int[] searchRangeRat(int[] nums, int target) {
        //
        int start = search(nums, target);
        if (start == nums.length || nums[start] != target) {
            return new int[]{-1, -1};
        }
        // 最后一个为 >= (target + 1 ) - 1;
        int end = searchRat(nums, target + 1) - 1;
        return new int[]{start, end};
    }

    /**
     * @description: 二分查找100 力扣热题
     * <a href="https://leetcode.cn/problems/search-in-rotated-sorted-array/?envType=study-plan-v2&envId=top-100-liked">...</a>
     * 时间 O(LogN) 空间 O(1)
     * @author: xiaoxie
     * @date: 2025/6/1 下午10:39
     * @param: [nums, target]
     * @return: int
     **/
    public int search4(int[] nums, int target) {
        int left = -1;
        int right = nums.length;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (select_blue(nums, target, mid)) {
                right = mid;
            } else {
                left = mid;
            }
        }
        if (right == nums.length || nums[right] != target) {
            return -1;
        }
        return right;
    }

    /**
     * 1,2,3,4,5,6,7
     */
    private boolean select_blue(int[] nums, int target, int mid) {
        int n = nums.length;
        if (nums[mid] > nums[n - 1]) {
            return target > nums[n - 1] && nums[mid] >= target;
        } else {
            return target <= nums[mid] || target > nums[n - 1];
        }
    }

    /**
     * @description: 二分查找100 力扣热题
     * 153. 寻找旋转排序数组中的最小值
     * <a href="https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/description/?envType=study-plan-v2&envId=top-100-liked">...</a>
     * 时间 O(LogN) 空间 O(1)
     * @author: xiaoxie
     * @date: 2025/6/1 下午10:49
     * @param: [nums]
     * @return: int
     **/
    public int findMin4(int[] nums) {
        int left = -1;
        int right = nums.length - 1;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[nums.length - 1]) {
                left = mid;
            } else {
                right = mid;
            }
        }

        return nums[right];
    }

    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    /**
     * @description: 灵神 链表题(反转类型)
     * 206. 反转链表
     * <a href="https://leetcode.cn/problems/reverse-linked-list/description/">...</a>
     * 时间O(n) 空间 O(1)
     * @author: xiaoxie
     * @date: 2025/6/3 下午10:37
     * @param: [head]
     * @return: cn.xie.wrench.LeetCode.ListNode
     **/
    public ListNode reverseList(ListNode head) {
        ListNode cur = head;
        ListNode pre = null;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

    /**
     * @description: 灵神 链表题(反转类型)
     * 92. 反转链表 II
     * <a href="https://leetcode.cn/problems/reverse-linked-list-ii/description/">...</a>
     * 时间O(n) 空间 O(1)
     * @author: xiaoxie
     * @date: 2025/6/3 下午11:05
     * @param: [head, left, right]
     * @return: cn.xie.wrench.LeetCode.ListNode
     **/
    public ListNode reverseBetween(ListNode head, int left, int right) {
        // 因为头指针也有可能参与反转,所以使用个虚拟节点指向他
        // cur 为反转后的节点的下一个,pre为反转后的头节点
        ListNode dummy = new ListNode(-1, head);
        ListNode p = dummy;
        // 先计算出从哪里开始反转
        for (int i = 0; i < left - 1; i++) {
            p = p.next;
        }
        // pre.next = cur
        ListNode pre = null;
        ListNode cur = p.next;
        for (int i = 0; i < right - left + 1; i++) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        p.next.next = cur;
        p.next = pre;
        return dummy.next;
    }

    /**
     * @description: 灵神 链表题(反转类型)
     * 25. K 个一组翻转链表
     * <a href="https://leetcode.cn/problems/reverse-nodes-in-k-group/description/">...</a>
     * 时间 O(N) 空间 O(1)
     * @author: xiaoxie
     * @date: 2025/6/4 下午11:00
     * @param: [head, k]
     * @return: cn.xie.wrench.LeetCode.ListNode
     **/
    public ListNode reverseKGroup(ListNode head, int k) {
        int n = 0;
        ListNode dummy = new ListNode(-1, head);
        ListNode cur = head;
        while (cur != null) {
            cur = cur.next;
            n++;
        }
        cur = dummy.next;
        ListNode pre = null;
        ListNode p = dummy;
        while (n >= k) {
            n -= k;
            for (int i = 0; i < k; i++) {
                ListNode next = cur.next;
                cur.next = pre;
                pre = cur;
                cur = next;
            }
            ListNode pNext = p.next;
            p.next.next = cur;
            p.next = pre;
            p = pNext;
        }
        return dummy.next;
    }

    /**
     * @description: 灵神 链表题(反转类型)
     * 24. 两两交换链表中的节点
     * <a href="https://leetcode.cn/problems/swap-nodes-in-pairs/description/">...</a>
     * 时间 O(N) 空间 O(1)
     * @author: xiaoxie
     * @date: 2025/6/5 下午9:36
     * @param: [head]
     * @return: cn.xie.wrench.LeetCode.ListNode
     **/
    public ListNode swapPairs(ListNode head) {
        // 这一题其实就是2个一组翻转
        ListNode dummy = new ListNode(-1, head);
        ListNode p = dummy;
        ListNode cur = head;
        int n = 0;
        while (cur != null) {
            cur = cur.next;
            n++;
        }
        if (n <= 1) {
            return dummy.next;
        }
        cur = head;
        ListNode pre = null;
        while (n >= 2) {
            n -= 2;
            for (int i = 0; i < 2; i++) {
                ListNode next = cur.next;
                cur.next = pre;
                pre = cur;
                cur = next;
            }
            ListNode pnext = p.next;
            p.next.next = cur;
            p.next = pre;
            p = pnext;
        }
        return dummy.next;
    }

    /**
     * @description: 灵神 链表题(反转类型)
     * 445. 两数相加 II
     * <a href="https://leetcode.cn/problems/add-two-numbers-ii/description/">...</a>
     * 时间 O(N) 空间 O(1)
     * @author: xiaoxie
     * @date: 2025/6/5 下午10:16
     * @param: [l1, l2]
     * @return: cn.xie.wrench.LeetCode.ListNode
     **/
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode r1 = reverse(l1);
        ListNode r2 = reverse(l2);
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        int diff = 0;
        while (r1 != null || r2 != null) {
            int sum = (r1 == null ? 0 : r1.val) + (r2 == null ? 0 : r2.val);
            sum += diff;
            cur = cur.next = new ListNode(sum % 10);
            r1 = r1 == null ? null : r1.next;
            r2 = r2 == null ? null : r2.next;
            diff = sum / 10;
        }
        if (diff != 0) {
            cur.next = new ListNode(diff);
        }
        return reverse(dummy.next);
    }

    private ListNode reverse(ListNode head) {
        ListNode cur = head;
        ListNode pre = null;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

    /**
     * @description: 灵神 链表题(反转类型)
     * 2816. 翻倍以链表形式表示的数字
     * <a href="https://leetcode.cn/problems/double-a-number-represented-as-a-linked-list/description/">...</a>
     * 时间 O(N) 空间 O(1)
     * @author: xiaoxie
     * @date: 2025/6/5 下午10:31
     * @param: [head]
     * @return: cn.xie.wrench.LeetCode.ListNode
     **/
    public ListNode doubleIt(ListNode head) {
        // 翻转后相加就可以了
        ListNode r = reverse(head);
        int curry = 0;
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        while (r != null || curry != 0) {
            int sum = (r == null ? 0 : r.val + r.val) + curry;
            cur = cur.next = new ListNode(sum % 10);
            curry = sum / 10;
            r = r == null ? null : r.next;
        }
        return reverse(dummy.next);
    }

    /**
     * @description: 灵神 快慢指针(链表)
     * 876. 链表的中间结点
     * <a href="https://leetcode.cn/problems/middle-of-the-linked-list/description/">...</a>
     * 时间 O(N) 空间 O(1)
     * @author: xiaoxie
     * @date: 2025/6/6 下午9:41
     * @param: [head]
     * @return: cn.xie.wrench.LeetCode.ListNode
     **/
    public ListNode middleNode(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    /**
     * @description: 灵神 快慢指针(链表)
     * 141. 环形链表
     * <a href="https://leetcode.cn/problems/linked-list-cycle/description/">...</a>
     * 时间 O(N) 空间 O(1)
     * @author: xiaoxie
     * @date: 2025/6/6 下午9:44
     * @param: [head]
     * @return: boolean
     **/
    public boolean hasCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                return true;
            }
        }
        return false;
    }

    /**
     * @description: 灵神 快慢指针(链表)
     * 142. 环形链表 II
     * <a href="https://leetcode.cn/problems/linked-list-cycle-ii/description/">...</a>
     * 时间 O(N) 空间 O(1)
     * @author: xiaoxie
     * @date: 2025/6/6 下午9:53
     * @param: [head]
     * @return: cn.xie.wrench.LeetCode.ListNode
     **/
    public ListNode detectCycle(ListNode head) {
        /**
         head到环入口为 a
         入口到相遇点为 b
         相遇点到入口为 c
         2a + 2b = a + b + k(b + c)
         2a + 2b = a + b + b + c + (k-1)(b+c);
         a- c = (k-1)(b+c);  因为 k <= 1
         所以 a = c
         */
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                while (slow != head) {
                    slow = slow.next;
                    head = head.next;
                }
                return slow;
            }
        }
        return null;
    }

    private ListNode reverseNode(ListNode head) {
        ListNode cur = head;
        ListNode pre = null;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

    private ListNode searchMid(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    /**
     * @description: 灵神 快慢指针(链表)
     * 143. 重排链表
     * <a href="https://leetcode.cn/problems/reorder-list/description/">...</a>
     * 时间 O(N) 空间 O(1)
     * @author: xiaoxie
     * @date: 2025/6/6 下午10:16
     * @param: [head]
     * @return: void
     **/
    public void reorderList(ListNode head) {
        /**
         先找到中间节点
         再翻转
         在和翻转后的节点进行差错插入
         */
        ListNode head2 = reverseNode(searchMid(head));
        // head1 = 1  1 2   head2 = 5  5 4 3
        // n1 = 2      n2 = 4
        // 1-5-2-4-3
        while (head2.next != null) {
            ListNode next1 = head.next;
            ListNode next2 = head2.next;
            head.next = head2;
            head2.next = next1;
            head = next1;
            head2 = next2;
        }

    }

    /**
     * @description: 灵神 快慢指针(链表)
     * 234. 回文链表
     * <a href="https://leetcode.cn/problems/palindrome-linked-list/description/">...</a>
     * 时间 O(N) 空间 O(1)
     * @author: xiaoxie
     * @date: 2025/6/6 下午10:33
     * @param: [head]
     * @return: boolean
     **/
    public boolean isPalindrome(ListNode head) {
        /**
         找到中间节点
         翻转
         遍历
         */
        ListNode head2 = reverseNode(searchMid(head));
        while (head2 != null) {
            if (head2.val != head.val) {
                return false;
            }
            head = head.next;
            head2 = head2.next;
        }
        return true;
    }

    /**
     * @description: 灵神 快慢指针(链表)
     * 2130. 链表最大孪生和
     * <a href="https://leetcode.cn/problems/maximum-twin-sum-of-a-linked-list/description/">...</a>
     * 时间 O(N) 空间 O(1)
     * @author: xiaoxie
     * @date: 2025/6/6 下午10:42
     * @param: [head]
     * @return: int
     **/
    public int pairSum(ListNode head) {
        /**
         n = 4
         i 孪生 (n-1-i)
         1       2
         找中间节点
         翻转
         遍历取最大
         */
        ListNode head2 = reverseNode(searchMid(head));
        int res = 0;
        while (head2 != null) {
            res = Math.max(head2.val + head.val, res);
            head = head.next;
            head2 = head2.next;
        }
        return res;
    }

    /**
     * @description: 灵神 前后指针 删除节点(链表)
     * 237. 删除链表中的节点
     * <a href="https://leetcode.cn/problems/delete-node-in-a-linked-list/description/">...</a>
     * 时间 O(1) 空间 O(1)
     * @author: xiaoxie
     * @date: 2025/6/6 下午10:54
     * @param: [node]
     * @return: void
     **/
    public void deleteNode(ListNode node) {
        node.val = node.next.val;
        node.next = node.next.next;
    }

    /**
     * @description: 灵神 前后指针 删除节点(链表)
     * 19. 删除链表的倒数第 N 个结点
     * <a href="https://leetcode.cn/problems/remove-nth-node-from-end-of-list/description/">...</a>
     * 时间 O(N) 空间 O(1)
     * @author: xiaoxie
     * @date: 2025/6/6 下午11:00
     * @param: [head, n]
     * @return: cn.xie.wrench.LeetCode.ListNode
     **/
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(-1, head);
        ListNode right = dummy;
        for (int i = 0; i < n; i++) {
            right = right.next;
        }
        ListNode left = dummy;
        while (right.next != null) {
            left = left.next;
            right = right.next;
        }
        left.next = left.next.next;
        return dummy.next;
    }

    /**
     * @description: 灵神 前后指针 删除节点(链表)
     * 83. 删除排序链表中的重复元素
     * <a href="https://leetcode.cn/problems/remove-duplicates-from-sorted-list/description/">...</a>
     * 时间 O(N) 空间 O(1)
     * @author: xiaoxie
     * @date: 2025/6/6 下午11:07
     * @param: [head]
     * @return: cn.xie.wrench.LeetCode.ListNode
     **/
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode cur = head;
        while (cur.next != null) {
            if (cur.next.val == cur.val) {
                while (cur.next != null && cur.next.val == cur.val) {
                    cur.next = cur.next.next;
                }
            } else {
                cur = cur.next;
            }
        }
        return head;
    }

    /**
     * @description: 灵神 前后指针 删除节点(链表)
     * 82. 删除排序链表中的重复元素 II
     * <a href="https://leetcode.cn/problems/remove-duplicates-from-sorted-list-ii/description/">...</a>
     * 时间 O(N) 空间 O(1)
     * @author: xiaoxie
     * @date: 2025/6/6 下午11:15
     * @param: [head]
     * @return: cn.xie.wrench.LeetCode.ListNode
     **/
    public ListNode deleteDuplicates2(ListNode head) {
        ListNode dummy = new ListNode(-1, head);
        ListNode cur = dummy;
        while (cur.next != null && cur.next.next != null) {
            int val = cur.next.val;
            if (cur.next.next.val == val) {
                while (cur.next != null && cur.next.val == val) {
                    cur.next = cur.next.next;
                }
            } else {
                cur = cur.next;
            }
        }
        return dummy.next;
    }

    /**
     * @description: 灵神 前后指针 删除节点(链表)
     * 203. 移除链表元素
     * <a href="https://leetcode.cn/problems/remove-linked-list-elements/description/">...</a>
     * 时间 O(N) 空间 O(1)
     * @author: xiaoxie
     * @date: 2025/6/6 下午11:22
     * @param: [head, val]
     * @return: cn.xie.wrench.LeetCode.ListNode
     **/
    public ListNode removeElements(ListNode head, int val) {
        ListNode dummy = new ListNode(-1, head);
        ListNode cur = dummy;
        while (cur.next != null) {
            int a = cur.next.val;
            if (a == val) {
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }
        return dummy.next;
    }

    /**
     * @description: 灵神 前后指针 删除节点(链表)
     * 3217. 从链表中移除在数组中存在的节点
     * <a href="https://leetcode.cn/problems/delete-nodes-from-linked-list-present-in-array/description/">...</a>
     * 时间 O(N) 空间 O(N)
     * @author: xiaoxie
     * @date: 2025/6/6 下午11:29
     * @param: [nums, head]
     * @return: cn.xie.wrench.LeetCode.ListNode
     **/
    public ListNode modifiedList(int[] nums, ListNode head) {
        Set<Integer> hash = new HashSet<>();
        for (int x : nums) {
            hash.add(x);
        }
        ListNode dummy = new ListNode(-1, head);
        ListNode cur = dummy;
        while (cur.next != null) {
            int val = cur.next.val;
            if (hash.contains(val)) {
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }
        return dummy.next;
    }

    /**
     * @description: 灵神 前后指针 删除节点(链表)
     * 2487. 从链表中移除节点
     * <a href="https://leetcode.cn/problems/remove-nodes-from-linked-list/description/">...</a>
     * 时间 O(N) 空间 O(1)
     * @author: xiaoxie
     * @date: 2025/6/6 下午11:41
     * @param: [head]
     * @return: cn.xie.wrench.LeetCode.ListNode
     **/
    public ListNode removeNodes(ListNode head) {
        /**
         8 - 3 -13 - 2 -5
         如果当前节点大于next节点就删除next节点
         */
        head = reverse(head);
        ListNode cur = head;
        while (cur.next != null) {
            int val = cur.val;
            if (val > cur.next.val) {
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }
        return reverse(head);
    }

    /**
     * @description: 灵神 前后指针 删除节点(链表)
     * 1669. 合并两个链表
     * <a href="https://leetcode.cn/problems/merge-in-between-linked-lists/description/">...</a>
     * 时间 O(N) 空间 O(1)
     * @author: xiaoxie
     * @date: 2025/6/6 下午11:47
     * @param: [list1, a, b, list2]
     * @return: cn.xie.wrench.LeetCode.ListNode
     **/
    public ListNode mergeInBetween(ListNode list1, int a, int b, ListNode list2) {
        /**
         找到要删除的前一个节点
         和后一个节点
         list2 直接插入就可以,当作删除了
         */
        ListNode left = list1;
        for (int i = 0; i < a - 1; i++) {
            left = left.next;
        }
        ListNode right = list1;
        for (int i = 0; i < b + 1; i++) {
            right = right.next;
        }
        left.next = list2;
        while (list2.next != null) {
            list2 = list2.next;
        }
        list2.next = right;
        return list1;
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    /**
     * @description: 灵神 二叉树递归
     * 104. 二叉树的最大深度
     * <a href="https://leetcode.cn/problems/maximum-depth-of-binary-tree/description/">...</a>
     * 时间 O(N) 空间 O(N)
     * @author: xiaoxie
     * @date: 2025/6/7 下午9:44
     * @param: [root]
     * @return: int
     **/
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }
    /**
     * @description: 灵神 二叉树递归
     * 111. 二叉树的最小深度
     * <a href="https://leetcode.cn/problems/minimum-depth-of-binary-tree/description/">...</a>
     * 时间 O(N) 空间 O(N)
     * @author: xiaoxie
     * @date: 2025/6/7 下午9:56
     * @param: [root]
     * @return: int
     **/
    public int minDepth(TreeNode root) {
        if(root == null) {
            return 0;
        }
        if(root.right == null) {
            return minDepth(root.left) + 1;
        }
        if(root.left == null) {
            return minDepth(root.right) + 1;
        }
        return Math.min(minDepth(root.left),minDepth(root.right)) + 1;
    }
    /**
     * @description: 灵神 二叉树递归
     * 112. 路径总和
     * <a href="https://leetcode.cn/problems/path-sum/description/">...</a>
     * 时间 O(N) 空间 O(N)
     * @author: xiaoxie
     * @date: 2025/6/7 下午10:16
     * @param: [root, targetSum]
     * @return: boolean
     **/
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if(root == null) {
            return false;
        }
        if(root.left == null && root.right == null) {
            return root.val == targetSum;
        }
        return hasPathSum(root.left,targetSum - root.val) || hasPathSum(root.right,targetSum - root.val);
    }
    /**
     * @description: 灵神 二叉树递归
     * 129. 求根节点到叶节点数字之和
     * <a href="https://leetcode.cn/problems/sum-root-to-leaf-numbers/description/">...</a>
     * 时间 O(N) 空间 O(N)
     * @author: xiaoxie
     * @date: 2025/6/7 下午10:27
     * @param: [root]
     * @return: int
     **/
    public int sumNumbers(TreeNode root) {
        return dfs(root,0);

    }
    private int dfs(TreeNode root,int num) {
        if(root == null) {
            return 0;
        }
        num = num * 10 + root.val;
        if(root.left == null && root.right == null) {
            return num;
        }

        return dfs(root.left,num) + dfs(root.right,num);
    }
    /**
     * @description: 灵神 二叉树递归
     * 1448. 统计二叉树中好节点的数目
     * <a href="https://leetcode.cn/problems/count-good-nodes-in-binary-tree/description/">...</a>
     * 时间 O(N) 空间 O(N)
     * @author: xiaoxie
     * @date: 2025/6/7 下午10:36
     * @param:
     * @return:
     **/
    int ans;
    public int goodNodes(TreeNode root) {
        dfs1(root,-0x3f3f3f3f);
        return ans;
    }
    private void dfs1(TreeNode root,int max) {
        if(root == null) {
            return;
        }
        if(root.val >= max) {
            max = root.val;
            ans++;
        }
        dfs1(root.left,max);
        dfs1(root.right,max);
    }
    /**
     * @description: 灵神 二叉树递归
     * 987. 二叉树的垂序遍历
     * <a href="https://leetcode.cn/problems/vertical-order-traversal-of-a-binary-tree/description/">...</a>
     * 时间复杂度：O(nlogn)，其中 n 为二叉树的节点个数。瓶颈在排序上。
     * 空间复杂度：O(n)。
     * @author: xiaoxie
     * @date: 2025/6/7 下午11:01
     * @param: [root]
     * @return: java.util.List<java.util.List < java.lang.Integer>>
     **/
    public List<List<Integer>> verticalTraversal(TreeNode root) {
        Map<Integer, List<int[]>> groups = new TreeMap<>();
        dfs(root, 0, 0, groups);

        List<List<Integer>> ans = new ArrayList<>(groups.size());
        for (List<int[]> g : groups.values()) {
            g.sort((a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);
            List<Integer> vals = new ArrayList<>(g.size());
            for (int[] p : g) {
                vals.add(p[1]);
            }
            ans.add(vals);
        }
        return ans;
    }
    private void dfs(TreeNode root,int row,int col,Map<Integer, List<int[]>> hash) {
        if(root ==null) {
            return;
        }
        // 前序遍历
        hash.computeIfAbsent(col, k -> new ArrayList<>()).add(new int[]{row, root.val});
        dfs(root.left,row + 1,col -1,hash);
        dfs(root.right,row + 1,col + 1,hash);
    }
    /**
     * @description: 力扣 100 热题 链表部分
     *  160. 相交链表
     *  <a href="https://leetcode.cn/problems/intersection-of-two-linked-lists/description/?envType=study-plan-v2&envId=top-100-liked">...</a>
     *  时间 O(N) 空间 O(1)
     * @author: xiaoxie
     * @date: 2025/6/8 下午9:29
     * @param: [headA, headB]
     * @return: cn.xie.wrench.LeetCode.ListNode
     **/
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        /**
         让长的先走a-b步,之后再一起走看是否相遇
         */
        int a = size(headA);
        int b = size(headB);
        if(b > a) {
            return getIntersectionNode(headB,headA);
        }
        ListNode right = headA;
        ListNode left = headB;
        for(int i = 0; i < a - b;i++) {
            right = right.next;
        }
        while(right != null && left != null) {
            if(right == left) {
                return right;
            }
            right = right.next;
            left = left.next;
        }
        return null;
    }
    private int size(ListNode head) {
        int ans = 0;
        while(head != null) {
            head = head.next;
            ans++;
        }
        return ans;
    }
    /**
     * @description: 力扣 100 热题 链表部分
     *  206. 反转链表
     *  <a href="https://leetcode.cn/problems/reverse-linked-list/description/?envType=study-plan-v2&envId=top-100-liked">...</a>
     *  时间 O(N) 空间 O(1)
     * @author: xiaoxie
     * @date: 2025/6/8 下午9:35
     * @param: [head]
     * @return: cn.xie.wrench.LeetCode.ListNode
     **/
    public ListNode reverseList1(ListNode head) {
        ListNode cur = head;
        ListNode pre = null;
        while(cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
    /**
     * @description: 力扣 100 热题 链表部分
     *  141. 环形链表
     *  <a href="https://leetcode.cn/problems/linked-list-cycle/description/?envType=study-plan-v2&envId=top-100-liked">...</a>
     *  时间 O(N) 空间 O(1)
     * @author: xiaoxie
     * @date: 2025/6/8 下午9:47
     * @param: [head]
     * @return: boolean
     **/
    public boolean hasCycle1(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if(slow == fast) {
                return true;
            }
        }
        return false;
    }
    /**
     * @description: 力扣 100 热题 链表部分
     * 142. 环形链表 II
     * <a href="https://leetcode.cn/problems/linked-list-cycle-ii/description/?envType=study-plan-v2&envId=top-100-liked">...</a>
     * 时间 O(N) 空间 O(1)
     * @author: xiaoxie
     * @date: 2025/6/8 下午9:51
     * @param: [head]
     * @return: cn.xie.wrench.LeetCode.ListNode
     **/
    public ListNode detectCycle2(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if(slow == fast) {
                while(head != slow) {
                    head = head.next;
                    slow = slow.next;
                }
                return slow;
            }
        }
        return null;
    }
    /**
     * @description: 力扣 100 热题 链表部分
     * 迭代法
     * 21. 合并两个有序链表
     * <a href="https://leetcode.cn/problems/merge-two-sorted-lists/description/?envType=study-plan-v2&envId=top-100-liked">...</a>
     * 时间 O(N) 空间 O(1)
     * @author: xiaoxie
     * @date: 2025/6/8 下午10:22
     * @param: [list1, list2]
     * @return: cn.xie.wrench.LeetCode.ListNode
     **/
    public ListNode mergeTwoLists1(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        while(list1 != null && list2 != null) {
            if(list1.val <= list2.val) {
                cur = cur.next = list1;
                list1 = list1.next;
            }else {
                cur = cur.next = list2;
                list2 = list2.next;
            }
        }
        cur.next = list1 != null ? list1 : list2; // 拼接剩余链表
        return dummy.next;
    }
    /**
     * @description: 力扣 100 热题 链表部分
     * 递归法
     * 21. 合并两个有序链表
     * <a href="https://leetcode.cn/problems/merge-two-sorted-lists/description/?envType=study-plan-v2&envId=top-100-liked">...</a>
     * 时间 O(N) 空间 O(N)
     * @author: xiaoxie
     * @date: 2025/6/8 下午10:22
     * @param: [list1, list2]
     * @return: cn.xie.wrench.LeetCode.ListNode
     **/
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1 == null) return list2;
        if(list2 == null) return list1;
        if(list1.val <= list2.val) {
            list1.next = mergeTwoLists(list1.next,list2);
            return list1;
        }
        list2.next = mergeTwoLists(list1,list2.next);
        return list2;
    }
    /**
     * @description: 力扣 100 热题 链表部分
     * 2. 两数相加
     * <a href="https://leetcode.cn/problems/add-two-numbers/description/?envType=study-plan-v2&envId=top-100-liked">...</a>
     * 时间 O(N) 空间 O(1)
     * @author: xiaoxie
     * @date: 2025/6/8 下午10:36
     * @param: [head1, head2]
     * @return: cn.xie.wrench.LeetCode.ListNode
     **/
    public ListNode addTwoNumbers3(ListNode head1, ListNode head2) {
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        int curry = 0;
        while(head1 != null || head2 != null || curry != 0) {
            int a = head1 != null ? head1.val : 0;
            curry += a;
            int b = head2 != null ? head2.val : 0;
            curry += b;
            cur = cur.next = new ListNode(curry % 10);
            curry /= 10;
            if(head1 != null) head1 = head1.next;
            if(head2 != null) head2 = head2.next;
        }

        return dummy.next;
    }
    /**
     * @description: 力扣 100 热题 链表部分
     * 19. 删除链表的倒数第 N 个结点
     * <a href="https://leetcode.cn/problems/remove-nth-node-from-end-of-list/description/?envType=study-plan-v2&envId=top-100-liked">...</a>
     * 时间 O(N) 空间 O(1)
     * @author: xiaoxie
     * @date: 2025/6/8 下午10:44
     * @param: [head, n]
     * @return: cn.xie.wrench.LeetCode.ListNode
     **/
    public ListNode removeNthFromEnd2(ListNode head, int n) {
        ListNode dummy = new ListNode(-1,head);
        ListNode right = dummy;
        ListNode left = dummy;
        for(int i = 0; i< n;i++) {
            right = right.next;
        }
        while(right.next!= null) {
            left = left.next;
            right = right.next;
        }
        left.next = left.next.next;
        return dummy.next;
    }
    /**
     * @description: 力扣 100 热题 链表部分
     * 24. 两两交换链表中的节点
     * <a href="https://leetcode.cn/problems/swap-nodes-in-pairs/description/?envType=study-plan-v2&envId=top-100-liked">...</a>
     * 时间 O(N) 空间 O(1)
     * @author: xiaoxie
     * @date: 2025/6/8 下午10:52
     * @param: [head]
     * @return: cn.xie.wrench.LeetCode.ListNode
     **/
    public ListNode swapPairs2(ListNode head) {
        ListNode dummy = new ListNode(-1,head);
        ListNode cur = head;
        int n = 0;
        while(cur != null) {
            cur = cur.next;
            n++;
        }
        cur = head;
        ListNode p = dummy;
        ListNode pre = null;
        while(n >= 2) {
            n -= 2;
            for(int i = 0;i < 2;i++) {
                ListNode next = cur.next;
                cur.next = pre;
                pre = cur;
                cur = next;
            }
            ListNode pnext = p.next;
            p.next.next = cur;
            p.next = pre;
            p = pnext;
        }
        return dummy.next;
    }
    /**
     * @description: 力扣 100 热题 链表部分
     * 25. K 个一组翻转链表
     * <a href="https://leetcode.cn/problems/reverse-nodes-in-k-group/description/?envType=study-plan-v2&envId=top-100-liked">...</a>
     * 时间 O(N) 空间 O(1)
     * @author: xiaoxie
     * @date: 2025/6/8 下午11:00
     * @param: [head, k]
     * @return: cn.xie.wrench.LeetCode.ListNode
     **/
    public ListNode reverseKGroup1(ListNode head, int k) {
        ListNode dummy = new ListNode(-1,head);
        ListNode cur = head;
        int n = 0;
        while(cur != null) {
            cur = cur.next;
            n++;
        }
        cur = head;
        ListNode p = dummy;
        ListNode pre = null;
        while(n >= k) {
            n-= k;
            for(int i = 0;i < k;i++) {
                ListNode next = cur.next;
                cur.next = pre;
                pre = cur;
                cur = next;
            }
            ListNode pnext = p.next;
            p.next.next = cur;
            p.next = pre;
            p = pnext;
        }
        return dummy.next;
    }
    class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }
    /**
     * @description: 力扣 100 热题 链表部分
     *  138. 随机链表的复制
     *  <a href="https://leetcode.cn/problems/copy-list-with-random-pointer/description/?envType=study-plan-v2&envId=top-100-liked">...</a>
     * 时间 O(N) 空间 O(1)
     * @author: xiaoxie
     * @date: 2025/6/10 下午8:45
     * @param: [head]
     * @return: cn.xie.wrench.LeetCode.Node
     **/
    public Node copyRandomList(Node head) {
        /**
         首先先把每个节点都加上复制节点
         */
        // a-a`-b-b`
        if(head == null) {
            return head;
        }
        Node cur = head;
        while(cur != null) {
            Node newHead = new Node(cur.val);
            newHead.next = cur.next;
            cur.next = newHead;
            cur = newHead.next;
        }
        // 复制随机指针
        cur = head;
        while(cur != null) {
            if(cur.random != null) {
                cur.next.random = cur.random.next;
            }
            cur = cur.next.next;
        }
        // a-a`-b-b` => a - b a` - b`
        cur = head.next;
        Node newHead = head.next;
        Node pre = head;
        while(cur.next != null) {
            pre.next = pre.next.next;
            cur.next = cur.next.next;
            cur = cur.next;
            pre = pre.next;
        }
        pre.next = null;
        return newHead;
    }
    /**
     * @description: 力扣 100 热题 链表部分
     * 归并排序
     * 148. 排序链表
     * <a href="https://leetcode.cn/problems/sort-list/description/?envType=study-plan-v2&envId=top-100-liked">...</a>
     * 时间复杂度：O(nlogn)，其中 n 是链表长度。递归式 T(n)=2T(n/2)+O(n)，由主定理可得时间复杂度为 O(nlogn)。
     * 空间复杂度：O(logn)。递归需要 O(logn) 的栈开销。
     * @author: xiaoxie
     * @date: 2025/6/10 下午9:11
     * @param: [head]
     * @return: cn.xie.wrench.LeetCode.ListNode
     **/
    public ListNode sortList(ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }
        ListNode mid = searchMid1(head);
        head = sortList(head);
        mid = sortList(mid);
        return marge(head,mid);
    }
    private ListNode searchMid1(ListNode head) {
        ListNode pre = head;
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null) {
            pre = slow;
            fast = fast.next.next;
            slow = slow.next;
        }
        pre.next = null;
        return slow;
    }
    private ListNode marge(ListNode l1,ListNode l2) {
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        while(l1 != null && l2 != null) {
            if(l1.val <= l2.val) {
                cur = cur.next = l1;
                l1 = l1.next;
            }else {
                cur = cur.next = l2;
                l2 = l2.next;
            }
        }
        cur.next = l1 == null ? l2 : l1;
        return dummy.next;
    }
    /**
     * @description: 力扣 100 热题 链表部分
     * 23. 合并 K 个升序链表
     * <a href="https://leetcode.cn/problems/merge-k-sorted-lists/description/?envType=study-plan-v2&envId=top-100-liked">...</a>
    时间复杂度：O(Llogm)，其中 m 为 lists 的长度，L 为所有链表的长度之和。每个节点参与链表合并的次数为 O(logm) 次，一共有 L 个节点，所以总的时间复杂度为 O(Llogm)。
    空间复杂度：O(logm)。递归深度为 O(logm)，需要 O(logm) 的栈空间。Python 忽略切片产生的额外空间。

     * @author: xiaoxie
     * @date: 2025/6/10 下午9:23
     * @param: [lists]
     * @return: cn.xie.wrench.LeetCode.ListNode
     **/
    public ListNode mergeKLists(ListNode[] lists) {
        return sortLists(lists,0,lists.length-1);
    }
    private ListNode sortLists(ListNode[] lists,int left,int right) {
        if(left > right) return null;
        if(left == right) return lists[left];
        int mid = left + (right - left) / 2;
        ListNode l1  = sortLists(lists,left,mid);
        ListNode l2 = sortLists(lists,mid + 1,right);
        return marge1(l1,l2);
    }
    public ListNode marge1(ListNode l1,ListNode l2) {
        if(l1 == null) return l2;
        if(l2 == null) return l1;
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        while(l1 != null && l2 != null) {
            if(l1.val < l2.val) {
                cur.next = l1;
                cur = cur.next;
                l1 = l1.next;
            }else {
                cur.next  = l2;
                cur = cur.next;
                l2 = l2.next;
            }
        }
        cur.next = (l1 != null ? l1 : l2);
        return dummy.next;
    }
    /**
     * @description: 力扣 100 热题 链表部分
     * 146. LRU 缓存
     * <a href="https://leetcode.cn/problems/lru-cache/description/?envType=study-plan-v2&envId=top-100-liked">...</a>
     *
     * @author: xiaoxie
     * @date: 2025/6/10 下午10:27
     * @param:
     * @return:
     **/
    class LRUCache {
        private static class Node{
            private Node next;
            private Node pre;
            private int key;
            private int value;
            public Node(int key,int value) {
                this.key = key;
                this.value = value;
            }

        }
        // 哨兵节点
        private final Node dummy = new Node(0,0);
        private final int capacity;
        private final Map<Integer,Node> hash = new HashMap<Integer,Node>();
        public LRUCache(int capacity) {
            this.capacity = capacity;
            // 设计成环形链表
            dummy.pre = dummy;
            dummy.next = dummy;
        }

        public int get(int key) {
            // 获取值并把节点变成第一个节点
            Node node = getNode(key);
            return node == null ? -1 : node.value;
        }

        public void put(int key, int value) {
            // 首先查看map是否有key映射的节点
            // 如果有就要替换value
            // 如果没有就正常尾插
            // 查看是否有超过容量
            Node node = getNode(key);
            Node newNode = new Node(key,value);
            if(node != null) {
                node.value = value;
                return;
            }
            hash.put(key,newNode);
            pushFront(newNode);
            if(hash.size() > capacity) {
                Node end = dummy.pre;
                hash.remove(end.key);
                remove(end);
            }
        }
        private Node getNode(int key) {
            // 先查询map看是否有如果有,就变成第一个节点
            if(hash.containsKey(key)) {
                Node node = hash.get(key);
                //先出链表中删除,后再添加到第一个节点
                remove(node);
                pushFront(node);
                return node;
            }
            return null;
        }
        private void remove(Node node) {
            node.pre.next = node.next;
            node.next.pre = node.pre;
        }
        // 头插
        private void pushFront(Node node) {
            // dummy -> node   dummy <-node node - > dummy.next   dummy.next.pre = node;
            node.next = dummy.next;
            dummy.next.pre = node;
            dummy.next = node;
            node.pre = dummy;
        }
    }
    class  LRUCacheandEx{
        private static class Node{
            private Node next;
            private Node pre;
            private int key;
            private int value;
            private long ex;
            Node(int key,int value) {
                this.key = key;
                this.value = value;
            }
            Node(int key,int value,long ex) {
                this.key = key;
                this.value = value;
                this.ex = ex;
            }
        }
        private final Node dummy = new Node(0,0);
        private int capacity;
        private long exTime;
        private final Map<Integer,Node> hash = new HashMap<>();
        public LRUCacheandEx(int capacity,long exTime) {
            this.capacity = capacity;
            this.exTime = exTime;
            // 设计成环形链表
            dummy.pre = dummy;
            dummy.next = dummy;
        }

        public int get(int key) {
            // 获取值并把节点变成第一个节点
            Node node = getNode(key);
            if(node == null) {
                return -1;
            }else {
                if(isEx(node.ex)) {
                    remove(node);
                    hash.remove(node.key);
                    return -1;
                }else {
                    return node.value;
                }
            }
        }
        public void put(int key, int value) {
            // 首先查询hash是否有节点存在
            // 如果存在,那么更新value
            // 如果不存在,头插
            // 查看是否超过容量,并且检查整个链表是否有过期的节点
            Node node = getNode(key);
            if(node != null) {
                node.value = value;
                node.ex = exTime + System.currentTimeMillis();
                return;
            }
            Node newNode = new Node(key,value,System.currentTimeMillis() + exTime);
            hash.put(key,newNode);
            pushFront(newNode);
            if(hash.size() > capacity) {
                Node cur = dummy.next;
                while(cur != dummy) {
                    Node next = cur.next;
                    if (isEx(cur.ex)) {
                        remove(cur);
                        hash.remove(cur.key);
                    }
                    cur = next;
                }
                if(hash.size() > capacity) {
                    cur = dummy.pre;
                    hash.remove(cur.key);
                    remove(cur);
                }
            }

        }
        private Node getNode(int key) {
            if(hash.containsKey(key)) {
                Node node = hash.get(key);
                //先删除
                remove(node);
                //后头插
                pushFront(node);
                return node;
            }
            return null;
        }
        private void remove(Node node) {
            node.pre.next = node.next;
            node.next.pre = node.pre;
        }
        private void pushFront(Node node) {
            // dummy.next = node node.pre = dummy  dummy.next.pre = node, node.next = dummy.next;
            dummy.next.pre = node;
            node.next = dummy.next;
            dummy.next = node;
            node.pre = dummy;
        }
        private boolean isEx(long ex) {
            return ex < System.currentTimeMillis();
        }
    }
    /**
     * @description: 灵神 二叉树部分
     * 100. 相同的树
     * <a href="https://leetcode.cn/problems/same-tree/description/">...</a>
     *  时间 O(N) 空间 (N)
     * @author: xiaoxie
     * @date: 2025/6/12 下午9:42
     * @param: [p, q]
     * @return: boolean
     **/
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null || q == null) {
            return p == q;
        }
        return p.val == q.val && isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
    }
    /**
     * @description: 灵神 二叉树部分
     * 101. 对称二叉树
     * <a href="https://leetcode.cn/problems/symmetric-tree/description/">...</a>
     * 时间 O(N) 空间 (N)
     * @author: xiaoxie
     * @date: 2025/6/12 下午9:47
     * @param: [root]
     * @return: boolean
     **/
    public boolean isSymmetric(TreeNode root) {
        return isSame(root.left,root.right);
    }
    private boolean isSame(TreeNode p,TreeNode q) {
        if(p == null || q == null) {
            return p == q;
        }
        return p.val == q.val && isSame(p.left,q.right) && isSame(p.right,q.left);
    }
    /**
     * @description: 灵神 二叉树部分
     * 110. 平衡二叉树
     * <a href="https://leetcode.cn/problems/balanced-binary-tree/description/">...</a>
     * 时间 O(N) 空间 (N)
     * @author: xiaoxie
     * @date: 2025/6/12 下午9:53
     * @param: [root]
     * @return: boolean
     **/
    public boolean isBalanced(TreeNode root) {
        return dfs(root) != -1;
    }
    private int dfs(TreeNode root) {
        if(root == null) {
            return 0;
        }
        int left = dfs(root.left);
        if(left == -1) {
            return -1;
        }
        int right = dfs(root.right);
        if(right == -1 || Math.abs(right - left) > 1) {
            return -1;
        }
        return Math.max(left,right) + 1;
    }

    /**
     * @description: 灵神 二叉树部分
     * 199. 二叉树的右视图
     * <a href="https://leetcode.cn/problems/binary-tree-right-side-view/description/">...</a>
     * 时间 O(N) 空间 (N)
     * @author: xiaoxie
     * @date: 2025/6/12 下午9:58
     * @param:
     * @return:
     **/
    List<Integer> ans1 = new ArrayList<>();
    public List<Integer> rightSideView(TreeNode root) {
        dfs11(root,0);
        return ans1;
    }
    private void dfs11(TreeNode root,int depth) {
        if(root == null) {
            return;
        }
        if(ans1.size() == depth) {
            ans1.add(root.val);
        }
        dfs11(root.right,depth + 1);
        dfs11(root.left,depth + 1);
    }
    /**
     * @description: 灵神 二叉树部分
     * 965. 单值二叉树
     * <a href="https://leetcode.cn/problems/univalued-binary-tree/description/">...</a>
     * 时间 O(N) 空间 (N)
     * @author: xiaoxie
     * @date: 2025/6/15 下午8:41
     * @param: [root]
     * @return: boolean
     **/
    public boolean isUnivalTree(TreeNode root) {
        return dfs12(root,root.val);
    }
    private boolean dfs12(TreeNode root,int val) {
        if(root == null) {
            return true;
        }
        if(root.val != val) {
            return false;
        }
        return dfs12(root.left,root.val) && dfs12(root.right,root.val);
    }
    /**
     * @description: 灵神 二叉树部分
     * 951. 翻转等价二叉树
     * <a href="https://leetcode.cn/problems/flip-equivalent-binary-trees/description/">...</a>
     * 时间 O(N) 空间 (N)
     * @author: xiaoxie
     * @date: 2025/6/15 下午8:53
     * @param: [root1, root2]
     * @return: boolean
     **/
    public boolean flipEquiv(TreeNode root1, TreeNode root2) {
        if (root1 == null || root2 == null) {
            return root1 == root2;
        }
        if (root1.val != root2.val) {
            return false;
        }
        // 要么是对称,要么是相等
        return flipEquiv(root1.left, root2.right) && flipEquiv(root1.right, root2.left)
                || flipEquiv(root1.left, root2.left) && flipEquiv(root1.right, root2.right);
    }
    /**
     * @description: 灵神 二叉树部分
     * 617. 合并二叉树
     * <a href="https://leetcode.cn/problems/merge-two-binary-trees/description/">...</a>
     * 时间 O(N) 空间 (N)
     * @author: xiaoxie
     * @date: 2025/6/15 下午9:21
     * @param: [root1, root2]
     * @return: cn.xie.wrench.LeetCode.TreeNode
     **/
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if(root1 == null && root2 == null) {
            return null;
        }
        if(root1 == null) return root2;
        if(root2 == null) return root1;
        TreeNode newHead = new TreeNode(root1.val + root2.val);
        newHead.left = mergeTrees(root1.left,root2.left);
        newHead.right = mergeTrees(root1.right,root2.right);
        return newHead;
    }
    /**
     * @description: 灵神 二叉树部分
     * 2331. 计算布尔二叉树的值
     * <a href="https://leetcode.cn/problems/evaluate-boolean-binary-tree/description/">...</a>
     * 时间 O(N) 空间 (N)
     * @author: xiaoxie
     * @date: 2025/6/15 下午9:27
     * @param: [root]
     * @return: boolean
     **/
    public boolean evaluateTree(TreeNode root) {
        if(root == null) {
            return true;
        }
        if(root.left == root.right) {
            return root.val == 1;
        }
        if(root.val == 3) {
            return evaluateTree(root.left) && evaluateTree(root.right);
        }else {
            return evaluateTree(root.left) || evaluateTree(root.right);
        }
    }
    /**
     * @description: 灵神 二叉树部分
     * 508. 出现次数最多的子树元素和
     * <a href="https://leetcode.cn/problems/most-frequent-subtree-sum/description/">...</a>
     * 时间 O(N) 空间 (N)
     * @author: xiaoxie
     * @date: 2025/6/15 下午9:53
     * @param:
     * @return:
     **/
    Map<Integer,Integer> hash = new HashMap<>();
    int max;
    public int[] findFrequentTreeSum(TreeNode root) {
        dfs13(root);
        List<Integer> list = new ArrayList<>();
        for(Map.Entry<Integer,Integer> entry : hash.entrySet()) {
            int sum = entry.getKey();
            int count = entry.getValue();
            if(count == max) {
                list.add(sum);
            }
        }
        int[] result = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            result[i] = list.get(i);
        }
        return result;
    }
    private int dfs13(TreeNode root) {
        if(root == null) {
            return 0;
        }
        int sum = root.val + dfs13(root.left) + dfs13(root.right);
        hash.put(sum,hash.getOrDefault(sum,0) + 1);
        max = Math.max(max,hash.get(sum));
        return sum;
    }
    /**
     * @description: 灵神 二叉树部分
     * 1026. 节点与其祖先之间的最大差值
     * <a href="https://leetcode.cn/problems/maximum-difference-between-node-and-ancestor/description/">...</a>
     * 时间 O(N) 空间 (N)
     * @author: xiaoxie
     * @date: 2025/6/15 下午10:11
     * @param: [root]
     * @return: int
     **/
    public int maxAncestorDiff(TreeNode root) {
        return dfs15(root,root.val,root.val);
    }
    private int dfs15(TreeNode root,int min,int max) {
        if(root == null) {
            return 0;
        }
        max = Math.max(max,root.val);
        min = Math.min(min,root.val);
        int diff = Math.max(Math.abs(max - root.val),Math.abs(min - root.val));
        diff = Math.max(diff,dfs15(root.left,min,max));
        diff = Math.max(diff,dfs15(root.right,min,max));
        return diff;
    }
    /**
     * @description: 灵神 二叉树部分
     *  1372. 二叉树中的最长交错路径
     *  <a href="https://leetcode.cn/problems/longest-zigzag-path-in-a-binary-tree/description/">...</a>
     *  时间 O(N) 空间 (N)
     * @author: xiaoxie
     * @date: 2025/6/15 下午10:43
     * @param: [root]
     * @return: int
     **/
    public int longestZigZag(TreeNode root) {
        // 如果往左走那么如果继续往左走,那么路径归零,如果往右走就+ 1;
        return Math.max(dfs14(root.left,0,true),dfs14(root.right,0,false));
    }
    private int dfs14(TreeNode root,int len,boolean left) {
        if(root == null) {
            return len;
        }
        if(left) {
            return Math.max(dfs14(root.left,0,true),dfs14(root.right,len + 1,false));
        }else {
            return Math.max(dfs14(root.left,len + 1,true),dfs14(root.right,0,false));
        }
    }
    /**
     * @description: 灵神 二叉树部分
     * 1080. 根到叶路径上的不足节点
     * <a href="https://leetcode.cn/problems/insufficient-nodes-in-root-to-leaf-paths/description/">...</a>
     * 时间 O(N) 空间 (N)
     * @author: xiaoxie
     * @date: 2025/6/15 下午10:52
     * @param: [root, limit]
     * @return: cn.xie.wrench.LeetCode.TreeNode
     **/
    public TreeNode sufficientSubset(TreeNode root, int limit) {
        return dfs16(root, 0, limit) ? root : null;
    }
    private boolean dfs16(TreeNode root,int sum ,int limit) {
        if(root == null) {
            return false;
        }
        if(root.left == root.right) {
            return sum + root.val >= limit;
        }
        boolean left = dfs16(root.left,sum + root.val,limit);
        boolean right = dfs16(root.right,sum + root.val,limit);
        if(!left) {
            root.left = null;
        }
        if(!right) {
            root.right = null;
        }
        return left || right;
    }
    /**
     * @description: 灵神 关于二叉搜索树
     * 98. 验证二叉搜索树
     * <a href="https://leetcode.cn/problems/validate-binary-search-tree/description/">...</a>
     * 时间 O(N) 空间 (N) 前序遍历
     * @author: xiaoxie
     * @date: 2025/6/16 下午8:55
     * @param: [root]
     * @return: boolean
     **/
    public boolean isValidBST(TreeNode root) {
        return preDfs(root,-Long.MAX_VALUE,Long.MAX_VALUE);
    }
    private boolean preDfs(TreeNode root,long left,long right) {
        if(root == null) {
            return true;
        }
        long x = root.val;
        return x > left && x < right && preDfs(root.left,left,x) && preDfs(root.right,x,right);
    }
    /**
     * @description: 灵神 关于二叉搜索树
     * 98. 验证二叉搜索树
     * <a href="https://leetcode.cn/problems/validate-binary-search-tree/description/">...</a>
     * 时间 O(N) 空间 (N) 中序遍历
     * @author: xiaoxie
     * @date: 2025/6/16 下午9:01
     * @param:
     * @return:
     **/
    long pre = -Long.MAX_VALUE;
    public boolean isValidBST1(TreeNode root) {
        if(root == null) {
            return true;
        }
        if(!isValidBST1(root.left)) {
            return false;
        }
        if(root.val <= pre) {
            return false;
        }
        pre = root.val;
        return isValidBST1(root.right);
    }
    /**
     * @description: 灵神 关于二叉搜索树
     * 98. 验证二叉搜索树
     * <a href="https://leetcode.cn/problems/validate-binary-search-tree/description/">...</a>
     * 时间 O(N) 空间 (N) 后序遍历
     * @author: xiaoxie
     * @date: 2025/6/16 下午9:14
     * @param: [root]
     * @return: boolean
     **/
    public boolean isValidBST3(TreeNode root) {
        long[] ans = dfs17(root);
        return ans[0] != Long.MIN_VALUE;
    }
    private long[] dfs17(TreeNode root) {
        if(root == null) {
            return new long[]{Long.MAX_VALUE,Long.MIN_VALUE};
        }
        long[] left = dfs17(root.left);
        long[] right  = dfs17(root.right);
        long x = root.val;
        if(x <= left[1] || x >= right[0]) {
            return new long[]{Long.MIN_VALUE,Long.MAX_VALUE};
        }
        return new long[]{Math.min(x,left[0]),Math.max(x,right[1])};
    }
    /**
     * @description: 灵神 关于二叉搜索树
     * 700. 二叉搜索树中的搜索
     * <a href="https://leetcode.cn/problems/search-in-a-binary-search-tree/description/">...</a>
     * 时间 O(N) 空间 (N)
     * @author: xiaoxie
     * @date: 2025/6/16 下午9:33
     * @param: [root, val]
     * @return: cn.xie.wrench.LeetCode.TreeNode
     **/
    public TreeNode searchBST(TreeNode root, int val) {
        if(root == null || root.val == val) {
            return root;
        }
        int x = root.val;
        if(x < val) {
            return searchBST(root.right,val);
        }else {
            return searchBST(root.left,val);
        }
    }
    /**
     * @description: 灵神 关于二叉搜索树
     * 938. 二叉搜索树的范围和
     * <a href="https://leetcode.cn/problems/range-sum-of-bst/description/">...</a>
     * 时间 O(N) 空间 (N)
     * @author: xiaoxie
     * @date: 2025/6/16 下午9:52
     * @param: [root, low, high]
     * @return: int
     **/
    public int rangeSumBST(TreeNode root, int low, int high) {
        if(root == null) {
            return 0;
        }
        int x = root.val;
        if(x < low) {
            return rangeSumBST(root.right,low,high);
        }
        if(x > high) {
            return rangeSumBST(root.left,low,high);
        }
        return x + rangeSumBST(root.left,low,high) + rangeSumBST(root.right,low,high);
    }

    /**
     * @description: 灵神 关于二叉搜索树
     *  530. 二叉搜索树的最小绝对差
     *  <a href="https://leetcode.cn/problems/minimum-absolute-difference-in-bst/description/">...</a>
     *   时间 O(N) 空间 (N)
     * @author: xiaoxie
     * @date: 2025/6/16 下午10:05
     * @param:
     * @return:
     **/
    int ans18 = 0x3f3f3f3f;
    int pre18 = -1;
    public int getMinimumDifference(TreeNode root) {
        dfs18(root);
        return ans;
    }
    private void dfs18(TreeNode root) {
        if(root == null) {
            return;
        }
        dfs18(root.left);
        int x = root.val;
        if(pre18 == -1) {
            pre18 = x;
        } else {
            ans18 = Math.min(ans18,Math.abs(x-pre18));
            pre18 = x;
        }
        dfs18(root.right);
    }
    /**
     * @description: 灵神 关于二叉搜索树
     * 2476. 二叉搜索树最近节点查询
     * <a href="https://leetcode.cn/problems/closest-nodes-queries-in-a-binary-search-tree/description/">...</a>
     *  时间 O(N) 空间 (N)
     * @author: xiaoxie
     * @date: 2025/6/17 下午9:30
     * @param:
     * @return:
     **/
    List<Integer> list = new ArrayList<>();
    public List<List<Integer>> closestNodes(TreeNode root, List<Integer> queries) {
        dfs19(root);
        List<List<Integer>> res =  new ArrayList<>(queries.size()); // 预分配空间
        int n = list.size();
        for(int q : queries) {
            int end = search(list,q);
            int max = end == n ? -1 : list.get(end);
            if(end == n || list.get(end) != q) {
                end--;
            }
            int min = end >= 0 ? list.get(end) : -1;
            res.add(List.of(min,max));
        }
        return res;

    }
    private void dfs19(TreeNode root) {
        if(root == null) {
            return;
        }
        dfs19(root.left);
        list.add(root.val);
        dfs19(root.right);
    }
    private int search(List<Integer> nums,int target) {
        int left = -1;
        int right = nums.size();
        while(left + 1 < right) {
            int mid = left + (right - left) / 2;
            if(nums.get(mid) >= target) {
                right = mid;
            }else {
                left = mid;
            }
        }
        return right;
    }
    /**
     * @description: 灵神 关于二叉搜索树
     *  501. 二叉搜索树中的众数
     *  <a href="https://leetcode.cn/problems/find-mode-in-binary-search-tree/description/">...</a>
     *  时间 O(N) 空间 (N)
     * @author: xiaoxie
     * @date: 2025/6/17 下午9:56
     * @param:
     * @return:
     **/
    List<Integer> nums = new ArrayList<>();
    int num = 0;
    int cur = 0;
    int count = 0;
    public int[] findMode(TreeNode root) {
        dfs20(root);
        int[] res = new int[nums.size()];
        for(int i = 0;i < nums.size();i++) {
            res[i] = nums.get(i);
        }
        return res;
    }
    private void dfs20(TreeNode root) {
        if(root == null) {
            return;
        }
        dfs20(root.left);
        select(root.val);
        dfs20(root.right);
    }
    private void select(int x) {
        if(x == num) {
            cur++;
        }else {
            cur = 1;
            num = x;
        }
        if(cur == count) {
            nums.add(x);
        }
        if(cur > count) {
            num = x;
            count = cur;
            nums.clear();
            nums.add(x);
        }

    }
    /**
     * @description: 灵神 关于二叉搜索树
     * 230. 二叉搜索树中第 K 小的元素
     * <a href="https://leetcode.cn/problems/kth-smallest-element-in-a-bst/description/">...</a>
     * 时间 O(N) 空间 (N)
     * @author: xiaoxie
     * @date: 2025/6/17 下午10:06
     * @param:
     * @return:
     **/
    List<Integer> ans21 = new ArrayList<>();
    int res21;
    public int kthSmallest(TreeNode root, int k) {
        dfs21(root,k);
        return res21;
    }
    private void dfs21(TreeNode root, int k) {
        if(root == null) {
            return;
        }
        dfs21(root.left,k);
        ans21.add(root.val);
        if(ans21.size() == k) {
            res21 = ans21.get(k-1);
            return;
        }

        dfs21(root.right,k);
    }
    /**
     * @description: 灵神 关于二叉搜索树
     * 1373. 二叉搜索子树的最大键值和
     * <a href="https://leetcode.cn/problems/maximum-sum-bst-in-binary-tree/description/">...</a>
     * 时间 O(N) 空间 (N)
     * @author: xiaoxie
     * @date: 2025/6/17 下午10:32
     * @param:
     * @return:
     **/
    int res22;
    public int maxSumBST(TreeNode root) {
        dfs21(root);
        return res22;
    }
    // 一边判断是否为二叉搜索树,一边算最大值[min,max,s]
    private int[] dfs21(TreeNode root) {
        if(root == null) {
            return new int[]{Integer.MAX_VALUE,Integer.MIN_VALUE,0};
        }
        int[] left = dfs21(root.left);
        int[] right = dfs21(root.right);
        int x = root.val;
        if(x <= left[1] || x >= right[0]) {
            return new int[]{Integer.MIN_VALUE,Integer.MAX_VALUE,0};
        }
        int s = x + left[2] + right[2];
        res22 = Math.max(s,res22);
        return new int[]{Math.min(x,left[0]),Math.max(x,right[1]),s};
    }
    /**
     * @description: 灵神 关于二叉搜索树
     * 105. 从前序与中序遍历序列构造二叉树
     * <a href="https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/">...</a>
     * 时间 O(N) 空间 (N)
     * @author: xiaoxie
     * @date: 2025/6/18 下午10:49
     * @param: [preorder, inorder]
     * @return: cn.xie.wrench.LeetCode.TreeNode
     **/
    public   TreeNode buildTree(int[] preorder, int[] inorder) {
        /**
         前: 根左右
         中: 左根右
         */
        int n = preorder.length;
        Map<Integer,Integer> hash = new HashMap<>(n);
        for(int i = 0;i < n;i++) {
            hash.put(inorder[i],i);
        }
        return dfs(preorder,0,n,0,n,hash);
    }
    private  TreeNode dfs(int[] preorder,int preL,int preR,int inL,int inR,Map<Integer,Integer> hash) {
        if(preL == preR) {
            return null;
        }
        // 左子树长度
        int leftSize = hash.get(preorder[preL]) - inL;
        TreeNode left = dfs(preorder,preL + 1,preL + leftSize + 1,inL,inL + leftSize,hash);
        TreeNode right = dfs(preorder,preL + 1 + leftSize,preR,inL + 1 + leftSize,inR,hash);
        return new TreeNode(preorder[preL],left,right);
    }
    /**
     * @description: 灵神 关于二叉搜索树
     * 1110. 删点成林
     * <a href="https://leetcode.cn/problems/delete-nodes-and-return-forest/">...</a>
     * 时间复杂度：O(n+m)，其中 n 为二叉树的节点个数，m 为 toDelete 的长度。每个节点都会递归恰好一次。
     * 空间复杂度：O(n+m)。最坏情况下，二叉树是一条链，递归需要 O(n) 的栈空间。
     * @author: xiaoxie
     * @date: 2025/6/21 下午10:13
     * @param: [root, to_delete]
     * @return: java.util.List<cn.xie.wrench.LeetCode.TreeNode>
     **/
    public List<TreeNode> delNodes(TreeNode root, int[] to_delete) {
        Set<Integer> hash = new HashSet<>(to_delete.length);
        for(int x : to_delete) {
            hash.add(x);
        }
        List<TreeNode> ans = new ArrayList<>();
        if(dfs(ans,hash,root) != null) {
            ans.add(root);
        }
        return ans;
    }
    private TreeNode dfs(List<TreeNode> ans,Set<Integer> hash,TreeNode root) {
        if(root == null) {
            return null;
        }
        root.left = dfs(ans,hash,root.left);
        root.right = dfs(ans,hash,root.right);
        if(!hash.contains(root.val)) {
            return root;
        }
        if(root.left != null) {
            ans.add(root.left);
        }
        if(root.right != null) {
            ans.add(root.right);
        }
        return null;
    }
    /**
     * @description: 灵神 二叉树公共祖先
     * 236. 二叉树的最近公共祖先
     * <a href="https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/description/">...</a>
     * 时间 O(N) 空间 (N)
     * @author: xiaoxie
     * @date: 2025/6/21 下午10:38
     * @param: [root, p, q]
     * @return: cn.xie.wrench.LeetCode.TreeNode
     **/
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        /**
         如果当前节点为null,或者等于p,q的话,那么返回当前节点
         如果p,q在左右子树中,那么返回当前节点
         如果都在左子树中,那么就返回递归左子树的结果
         如果都在右子树中,那么返回递归右子树的结果
         如果都不在,那么那么返回空;
         */
        if(root == null || root == p || root == q) {
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left,p,q);
        TreeNode right = lowestCommonAncestor(root.right,p,q);
        if(left != null && right != null) {
            return root;
        }
        if(left != null) {
            return left;
        }else {
            return right;
        }
    }
    /**
     * @description: 灵神 二叉树公共祖先
     * 235. 二叉搜索树的最近公共祖先
     * <a href="https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/description/">...</a>
     * 时间 O(N) 空间 (N)
     * @author: xiaoxie
     * @date: 2025/6/21 下午10:44
     * @param: [root, p, q]
     * @return: cn.xie.wrench.LeetCode.TreeNode
     **/
    public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
        /**
         如果p.val 和 q.val > root.val 那么说明在右子树中递归右子树即可
         如果p.val 和 q.val < root.val 那么说明在左子树中递归左子树即可
         其余情况返回root即可
         */
        int x = root.val;
        if(p.val > x && q.val > x) {
            return lowestCommonAncestor1(root.right,p,q);
        }
        if(p.val < x && q.val < x) {
            return lowestCommonAncestor1(root.left,p,q);
        }
        return root;
    }

    /**
     * @description: 灵神 二叉树公共祖先
     * 1123. 最深叶节点的最近公共祖先
     * <a href="https://leetcode.cn/problems/lowest-common-ancestor-of-deepest-leaves/description/">...</a>
     * 时间 O(N) 空间 (N)
     * @author: xiaoxie
     * @date: 2025/6/21 下午11:02
     * @param:
     * @return:
     **/
    TreeNode ans31;
    int max31 = -1;
    public TreeNode lcaDeepestLeaves(TreeNode root) {
        dfs31(root,0);
        return ans31;
    }
    private int dfs31(TreeNode root,int depth) {
        if(root == null) {
            max31 = Math.max(max31,depth);
            return depth;
        }
        int left = dfs31(root.left,depth + 1);
        int right = dfs31(root.right,depth + 1);
        if(left == right && left == max) {
            ans31 = root;
        }
        return Math.max(left,right);
    }
    /**
     * @description: 灵神 二叉树公共祖先
     * 2096. 从二叉树一个节点到另一个节点每一步的方向
     * <a href="https://leetcode.cn/problems/step-by-step-directions-from-a-binary-tree-node-to-another/description/">...</a>
     * 时间 O(N) 空间 (N)
     * @author: xiaoxie
     * @date: 2025/6/21 下午11:24
     * @param: [root, startValue, destValue]
     * @return: java.lang.String
     **/
    public String getDirections(TreeNode root, int startValue, int destValue) {
        /**
         先找到s和 dest的公共祖先;
         */
        TreeNode lca = top(root,startValue,destValue);
        StringBuilder pathToStart = new StringBuilder();
        findPath(lca, startValue, pathToStart);
        StringBuilder pathToDest = new StringBuilder();
        findPath(lca, destValue, pathToDest);
        return "U".repeat(pathToStart.length()) + pathToDest.toString();
    }
    private boolean findPath(TreeNode node, int target, StringBuilder path) {
        if (node == null) {
            return false; // 遍历到底，返回 false
        }
        if (node.val == target) {
            return true; // 找到目标，返回 true
        }

        // 先尝试左子树
        path.append("L");
        if (findPath(node.left, target, path)) {
            return true;
        }
        path.deleteCharAt(path.length() - 1); // 回溯

        // 再尝试右子树
        path.append("R");
        if (findPath(node.right, target, path)) {
            return true;
        }
        path.deleteCharAt(path.length() - 1); // 回溯
        return false; // 目标不在该子树
    }
    private TreeNode top(TreeNode root,int s,int end) {
        if(root == null || root.val == s || root.val == end) {
            return root;
        }
        TreeNode left = top(root.left,s,end);
        TreeNode right = top (root.right,s,end);
        if(left != null && right != null) {
            return root;
        }
        if(left != null) {
            return left;
        }else {
            return right;
        }
    }
    /**
     * @description: 灵神 二叉树 BFS
     * 102. 二叉树的层序遍历
     * <a href="https://leetcode.cn/problems/binary-tree-level-order-traversal/description/">...</a>
     * 时间 O(N) 空间 (N)
     * @author: xiaoxie
     * @date: 2025/6/21 下午11:52
     * @param: [root]
     * @return: java.util.List<java.util.List < java.lang.Integer>>
     **/
    public List<List<Integer>> levelOrder(TreeNode root) {
        if(root == null) {
            return List.of();
        }
        List<List<Integer>> ans = new ArrayList<>();
        Queue<TreeNode> q = new ArrayDeque<>();
        q.add(root);
        while(!q.isEmpty()) {
            List<Integer> temp = new ArrayList<>();
            int n = q.size();
            while(n -- > 0) {
                TreeNode cur = q.poll();
                temp.add(cur.val);
                if(cur.left != null) {
                    q.add(cur.left);
                }
                if(cur.right != null) {
                    q.add(cur.right);
                }
            }
            ans.add(new ArrayList<>(temp));
        }
        return ans;
    }
    /**
     * @description: 灵神 二叉树 BFS
     * 103. 二叉树的锯齿形层序遍历
     * <a href="https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/description/">...</a>
     * 时间 O(N) 空间 (N)
     * @author: xiaoxie
     * @date: 2025/6/22 上午12:17
     * @param: [root]
     * @return: java.util.List<java.util.List < java.lang.Integer>>
     **/
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        /**
         单数 尾插 Last
         双数 头插 First
         */
        if(root == null) {
            return List.of();
        }
        List<List<Integer>> ans =  new LinkedList<>();
        Queue<TreeNode>  q = new ArrayDeque<>();
        q.add(root);
        boolean flag = false;
        while (!q.isEmpty()) {
            int n = q.size();
            Deque<Integer> temp = new LinkedList<Integer>();
            while (n-- > 0) {
                TreeNode cur = q.poll();
                if(!flag) {
                    temp.offerLast(cur.val);
                }else {
                    temp.offerFirst(cur.val);
                }
                if(cur.left != null) q.add(cur.left);
                if(cur.right != null) q.add(cur.right);
            }
            ans.add(new LinkedList<>(temp));
            flag = !flag;
        }
        return ans;
    }
    /**
     * @description: 灵神 二叉树 BFS
     * 513. 找树左下角的值
     * <a href="https://leetcode.cn/problems/find-bottom-left-tree-value/description/">...</a>
     * 时间 O(N) 空间 (N)
     * @author: xiaoxie
     * @date: 2025/6/22 上午12:24
     * @param: [root]
     * @return: int
     **/
    public int findBottomLeftValue(TreeNode root) {
        /**
         先添加右,在添加左,最后一个就是左下角的值
         */
        Queue<TreeNode> q = new ArrayDeque<>();
        q.add(root);
        TreeNode cur = root;
        while(!q.isEmpty()) {
            cur = q.poll();
            if(cur.right != null) q.add(cur.right);
            if(cur.left != null) q.add(cur.left);
        }
        return cur.val;
    }
    /**
     * @description:
     * 513. 找树左下角的值
     * <a href="https://leetcode.cn/problems/find-bottom-left-tree-value/description/">...</a>
     * 时间 O(N) 空间 (N)
     * dfs写法
     * @author: xiaoxie
     * @date: 2025/6/22 上午12:33
     * @param:
     * @return:
     **/
    List<Integer> ans12 = new ArrayList<>();
    public int findBottomLeftValue2(TreeNode root) {
        dfs33(root,1);
        return ans12.get(ans12.size() -1);
    }
    private void dfs33(TreeNode root,int depth) {
        if(root == null) {
            return;
        }
        if(ans12.size() < depth) {
            ans12.add(root.val);
        }
        dfs33(root.left,depth + 1);
        dfs33(root.right,depth + 1);
    }
    /**
     * @description: 灵神 二叉树 BFS
     * 107. 二叉树的层序遍历 II
     * <a href="https://leetcode.cn/problems/binary-tree-level-order-traversal-ii/description/">...</a>
     * 时间 O(N) 空间 (N)
     * @author: xiaoxie
     * @date: 2025/6/22 下午9:17
     * @param: [root]
     * @return: java.util.List<java.util.List < java.lang.Integer>>
     **/
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        if(root == null) {
            return List.of();
        }
        List<List<Integer>> ans = new ArrayList<>();
        Queue<TreeNode> q = new ArrayDeque<>();
        q.add(root);
        while(!q.isEmpty()) {
            int n = q.size();
            List<Integer> temp = new ArrayList<>();
            while(n-- > 0) {
                TreeNode cur = q.poll();
                temp.add(cur.val);
                if(cur.left != null) q.add(cur.left);
                if(cur.right != null) q.add(cur.right);
            }
            ans.add(0,temp);
        }
        return ans;
    }
    /**
     * @description: 灵神 二叉树 BFS
     * 104. 二叉树的最大深度
     * <a href="https://leetcode.cn/problems/maximum-depth-of-binary-tree/description/">...</a>
     * 时间 O(N) 空间 (N)
     * @author: xiaoxie
     * @date: 2025/6/22 下午9:23
     * @param: [root]
     * @return: int
     **/
    public int maxDepth2(TreeNode root) {
        if(root == null) {
            return 0;
        }
        int depth = 0;
        Queue<TreeNode> q = new ArrayDeque<>();
        q.add(root);
        while(! q.isEmpty()) {
            int n = q.size();
            while(n -- > 0) {
                TreeNode cur = q.poll();
                if(cur.left != null) q.add(cur.left);
                if(cur.right != null) q.add(cur.right);
            }
            depth++;
        }
        return depth;
    }
    /**
     * @description: 灵神 二叉树 BFS
     * 111. 二叉树的最小深度
     * <a href="https://leetcode.cn/problems/minimum-depth-of-binary-tree/description/">...</a>
     * 时间 O(N) 空间 (N)
     * @author: xiaoxie
     * @date: 2025/6/22 下午9:36
     * @param: [root]
     * @return: int
     **/
    public int minDepth2(TreeNode root) {
        if(root == null) {
            return 0;
        }
        int ans = 0x3f3f3f3f;
        int depth = 0;
        Queue<TreeNode> q = new ArrayDeque<>();
        q.add(root);
        while(!q.isEmpty()) {
            int n = q.size();
            depth++;
            while(n-- > 0) {
                TreeNode cur = q.poll();
                if(cur.left == cur.right) {
                    ans = Math.min(depth,ans);
                }
                if(cur.left != null) q.add(cur.left);
                if(cur.right != null) q.add(cur.right);
            }
        }
        return ans;
    }
    /**
     * @description: 灵神 二叉树 BFS
     * 2583. 二叉树中的第 K 大层和
     * 时间 O(NLogK) 空间 (N)
     * @author: xiaoxie
     * @date: 2025/6/22 下午9:55
     * @param: [root, k]
     * @return: long
     **/
    public long kthLargestLevelSum(TreeNode root, int k) {
        PriorityQueue<Long> deep = new PriorityQueue<>();
        Queue<TreeNode> q = new ArrayDeque<>();
        q.add(root);
        while(!q.isEmpty()) {
            int n = q.size();
            long sum = 0L;
            while(n-- > 0) {
                TreeNode cur = q.poll();
                sum += cur.val;
                if(cur.left != null) q.add(cur.left);
                if(cur.right != null) q.add(cur.right);
            }
            if(deep.size() < k || sum > deep.peek()) {
                if(deep.size() == k) {
                    deep.poll();
                }
                deep.offer(sum);
            }
        }
        return deep.size() == k ? deep.peek() : -1;
    }
    /**
     * @description: 灵神 二叉树 BFS
     * 199. 二叉树的右视图
     * <a href="https://leetcode.cn/problems/binary-tree-right-side-view/description/">...</a>
     * 时间 O(N) 空间 (N)
     * @author: xiaoxie
     * @date: 2025/6/22 下午10:14
     * @param: [root]
     * @return: java.util.List<java.lang.Integer>
     **/
    public List<Integer> rightSideView2(TreeNode root) {
        if(root == null) {
            return List.of();
        }
        List<Integer> ans = new ArrayList<>();
        Queue<TreeNode> q = new ArrayDeque<>();
        q.add(root);
        int depth = 0;
        while(!q.isEmpty()) {
            int n = q.size();
            while(n-- > 0) {
                TreeNode cur = q.poll();
                if(depth == ans.size()) {
                    ans.add(cur.val);
                }
                if(cur.right != null) q.add(cur.right);
                if(cur.left != null) q.add(cur.left);
            }
            depth++;
        }
        return ans;
    }
    class Node1 {
        public int val;
        public Node1 left;
        public Node1 right;
        public Node1 next;

        public Node1() {}

        public Node1(int _val) {
            val = _val;
        }

        public Node1(int _val, Node1 _left, Node1 _right, Node1 _next) {
            val = _val;
            left = _left;
            right = _right;
            next = _next;
        }
    };
    /**
     * @description: 灵神 二叉树 BFS
     * 116. 填充每个节点的下一个右侧节点指针
     * <a href="https://leetcode.cn/problems/populating-next-right-pointers-in-each-node/description/">...</a>
     * 时间 O(N) 空间 (N)
     * @author: xiaoxie
     * @date: 2025/6/22 下午10:35
     * @param: [root]
     * @return: cn.xie.wrench.LeetCode.Node
     **/
    public Node1 connect(Node1 root) {
        if(root == null) {
            return root;
        }
        Queue<Node1> q = new ArrayDeque<>();
        q.add(root);
        while(!q.isEmpty()) {
            int n = q.size();
            while(n-- > 0) {
                Node1 cur = q.poll();
                if(n >= 1) {
                    cur.next = q.peek();
                }
                if(cur.left != null) q.add(cur.left);
                if(cur.right != null) q.add(cur.right);
            }
        }
        return root;
    }
    /**
     * @description:
     * 116. 填充每个节点的下一个右侧节点指针
     *<a href="https://leetcode.cn/problems/populating-next-right-pointers-in-each-node/description/">...</a>
     * 时间 O(N) 空间 (N)
     * dfs
     * @author: xiaoxie
     * @date: 2025/6/23 下午7:18
     * @param:
     * @return:
     **/
    List<Node1> list13 = new ArrayList<>();
    public Node1 connect2(Node1 root) {
        dfs36(root,0);
        return root;
    }
    private void dfs36(Node1 root,int depth) {
        if(root == null) {
            return;
        }
        if(depth == list13.size()) {
            list13.add(root);
        }else {
            list13.get(depth).next = root;
            list13.set(depth,root);
        }
        dfs36(root.left,depth + 1);
        dfs36(root.right,depth + 1);
    }
    /**
     * @description:
     * 116. 填充每个节点的下一个右侧节点指针
     *<a href="https://leetcode.cn/problems/populating-next-right-pointers-in-each-node/description/">...</a>
     * 时间 O(N) 空间 (1)
     * BFS + 链表
     * @author: xiaoxie
     * @date: 2025/6/23 下午9:55
     * @param: [root]
     * @return: cn.xie.wrench.LeetCode.Node1
     **/
    public Node1 connect3(Node1 root) {
        Node1 dummy = new Node1();
        Node1 cur = root;
        while(cur != null) {
            dummy.next = null; //下一层的开头
            Node1 next = dummy;
            while(cur != null) {
                if(cur.left != null) {
                    next.next = cur.left;
                    next = cur.left;
                }
                if(cur.right != null) {
                    next.next = cur.right;
                    next = cur.right;
                }
                cur = cur.next;
            }
            cur = dummy.next;
        }
        return root;
    }
    /**
     * @description: 灵神 二叉树 BFS
     * 1302. 层数最深叶子节点的和
     * <a href="https://leetcode.cn/problems/deepest-leaves-sum/description/">...</a>
     * 时间 O(N) 空间 (N)
     * @author: xiaoxie
     * @date: 2025/6/23 下午10:12
     * @param: [root]
     * @return: int
     **/
    public int deepestLeavesSum(TreeNode root) {
        Queue<TreeNode> q = new ArrayDeque<>();
        q.add(root);
        int ans = 0;
        int depth = 0;
        int max = -1;
        while(!q.isEmpty()) {
            int n = q.size();
            depth++;
            int sum = 0;
            while(n -- > 0) {
                TreeNode cur = q.poll();
                if(cur.left == cur.right) {
                    sum += cur.val;
                }
                if(cur.left != null) q.add(cur.left);
                if(cur.right != null) q.add(cur.right);
            }
            if(depth > max) {
                ans = sum;
                max = depth;
            }
        }
        return ans;
    }
    /**
     * @description: 灵神 二叉树 BFS
     * 1609. 奇偶树
     * <a href="https://leetcode.cn/problems/even-odd-tree/description/">...</a>
     * 时间 O(N) 空间 (N)
     * @author: xiaoxie
     * @date: 2025/6/23 下午10:27
     * @param: [root]
     * @return: boolean
     **/
    public boolean isEvenOddTree(TreeNode root) {
        /**
         偶数下标的值都为奇数,并且 严格递增
         奇数下标的值都为偶数,并且 严格递减
         */
        Queue<TreeNode> q = new ArrayDeque<>();
        boolean flag = true;
        q.add(root);
        while(!q.isEmpty()) {
            int n = q.size();
            while(n -- > 0) {
                TreeNode cur = q.poll();
                int x = cur.val;
                if(flag) {
                    if(x % 2 == 0) {
                        return false;
                    }
                    if(n >= 1) {
                        if(x >= q.peek().val) {
                            return false;
                        }
                    }
                }else {
                    if(x % 2 == 1) {
                        return false;
                    }
                    if(n >= 1) {
                        if(x <= q.peek().val) {
                            return false;
                        }
                    }
                }
                if(cur.left != null) q.add(cur.left);
                if(cur.right != null) q.add(cur.right);
            }
            flag = !flag;
        }
        return true;
    }
    /**
     * @description: 灵神 二叉树 BFS
     * 2415. 反转二叉树的奇数层
     * <a href="https://leetcode.cn/problems/reverse-odd-levels-of-binary-tree/description/">...</a>
     * 时间 O(N) 空间 (N)
     * @author: xiaoxie
     * @date: 2025/6/23 下午10:53
     * @param: [root]
     * @return: cn.xie.wrench.LeetCode.TreeNode
     **/
    public TreeNode reverseOddLevels(TreeNode root) {
        Queue<TreeNode> q = new ArrayDeque<>();
        q.add(root);
        boolean flag = true;
        while(!q.isEmpty()) {
            int n = q.size();
            List<TreeNode> list = new ArrayList<>();
            while(n -- > 0) {
                TreeNode cur = q.poll();
                if(!flag) {
                    list.add(cur);
                }
                if(cur.left != null) q.add(cur.left);
                if(cur.right != null) q.add(cur.right);
            }
            if(!flag) {
                for(int l = 0,r = list.size() -1;l < r;l++,r--) {
                    int temp = list.get(l).val;
                    list.get(l).val = list.get(r).val;
                    list.get(r).val = temp;
                }
            }
            flag = !flag;
        }
        return root;
    }
    /**
     * @description: 灵神 二叉树 BFS
     * 2641. 二叉树的堂兄弟节点 II
     * <a href="https://leetcode.cn/problems/cousins-in-binary-tree-ii/description/">...</a>
     * 时间 O(N) 空间 (N)
     * @author: xiaoxie
     * @date: 2025/6/23 下午11:12
     * @param: [root]
     * @return: cn.xie.wrench.LeetCode.TreeNode
     **/
    public TreeNode replaceValueInTree(TreeNode root) {
        Queue<TreeNode> q = new ArrayDeque<>();
        root.val = 0;
        q.add(root);
        while (!q.isEmpty()) {
            int sum = 0;
            int n = q.size();
            for (TreeNode cur : q) {
                if (cur.left != null) {
                    sum += cur.left.val;
                }
                if (cur.right != null) {
                    sum += cur.right.val;
                }
            }
            while (n-- > 0) {
                TreeNode cur = q.poll();
                int childSum = (cur.left == null ? 0 : cur.left.val) +
                        (cur.right == null ? 0 : cur.right.val);
                if (cur.left != null) {
                    cur.left.val = sum - childSum;
                    q.add(cur.left);
                }
                if (cur.right != null) {
                    cur.right.val = sum - childSum;
                    q.add(cur.right);
                }
            }
        }
        return root;
    }

}
